# Quicksort vs. insertion sort on linked list: performance

I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm. Does anyone have any idea why this is? Insertion sort has a complexity of $\Theta(n^2)$ and quicksort $O(n\log n)$ so therefore quicksort should be faster. I tried for random input size and it shows me the contrary. Strange...

Here the code in Java:

public static LinkedList qSort(LinkedList list) {

Node currentNode;
int size = list.getSize();

//Create new lists x smaller equal and y greater

if (size <= 1)
return list;
else {

Node pivot = getPivot(list);
// System.out.println("Pivot: " + pivot.value);

for (int i = 0; i <= size - 1; i++) {
//Check that the currentNode is not our pivot
if (currentNode != pivot) {
//Nodes with values smaller equal than the pivot goes in x
if (currentNode.value <= pivot.value) {
{
// System.out.print("Elements in x:");
// x.printList();
}

}
//Nodes with values greater than the pivot goes in y
else if (currentNode.value > pivot.value) {
if (currentNode != pivot) {
// System.out.print("Elements in y:");
// y.printList();
}
}
}
//Set the pointer to the next node
currentNode = currentNode.next;
}

//Recursive calls and concatenation of the Lists and pivot
return concatenateList(qSort(x), pivot, qSort(y));

}
}

• – Dave Clarke Apr 19 '12 at 12:20
• Why are you using linked lists? The bookkeeping for LLs is rather painful, and I don't think many people will disseminate your code to see if you got everything correct. For all we know, your implementation is horribly inefficient. LLs in general perform worse than vector-like implementations because their caching behavior is rather meh. This shouldn't make a difference between the two algorithms though. Lastly, if you claim that there is a performance difference, you will have to give us your exact method of measuring this before we can say anything useful about it. – Alex ten Brink Apr 19 '12 at 12:50
• @forrestGump: Could you pleas re-insert your code into the question? The replies make little sense now that no-one can see what you were actually doing. – Pedro Apr 19 '12 at 15:36
• Quicksort does not have complexity $O(n\log n)$! – Raphael Apr 19 '12 at 16:55
• @Pedro: You can see the code by clicking "edit" and looking at old versions, but if the implementation was like this one en.wikipedia.org/wiki/Quicksort#In-place_version except with $O(n)$ list operations replacing $O(1)$ array operations, it might be easier to just say so. – Louis Apr 19 '12 at 18:04

Pedro's answer covers what is going wrong with your first attempt. But I want to talk about a few things when it comes to analyzing algorithms that may be a bit subtle.

Before you can start analyzing an algorithm, you need to say exactly what you're doing. "Quicksort", for example, can mean a number of different things. The basic pattern is:

• Pick a pivot element
• Partition the input around the pivot
• Recursively sort the pieces
• Combine the sub-problems

Even at this level, there is some ambiguity, since I haven't actually described how to pick the pivot and how to partition. In the modern era, which probably means about 20 years, people think that you:

• Pick the pivot uniformly at random
• Parition into "less than", "equal", and "greater than" pieces

In which case the number of comparisons is $O(n\log n)$ in expectation and close to information theoretic bounds.

But! Notice that you and some commenters like to pick the pivot other ways, so it is still important to say what you really mean. Picking the pivot deterministically means that there are cases (depending on your rule) that will be much much worse.

Even once you've decided what you really want your algorithm to do, you need to think about the "basic steps". For quicksort we need:

• A way to pick the pivot
• A way to compare elements
• A way to partition
• A way to combine

Notice that most analysis of sorting devolves onto counting comparisons. We'll talk about why this is next.

How much do your primitives cost?

Finally, in any detailed running time analysis, you need some model of computation in which you can count "operations". The most popular model for algorithms is the "RAM" which has arrays with constant-time reads/writes, the usual arithmetic operations, and integer comparisons. (But there are lots of others.)

For the usual analysis of quicksort, on an input of length $n$, you'll want:

• Picking the pivot to be $O(n)$
• Partitioning to be $O(n)$
• Combining sub-arrays to be $O(n)$

You can do this with linked lists (as in your second try) or (more usually) arrays, but the actual implementations will be very different. The issue is that in your first try (according to other answers), you were spending $\Omega(n^2)$ on partitioning, which changes the complexity a lot.

Why sorting analyses usually just count comparisons.

The reason I wrote all of this down is that, even in your bad implementation, you weren't doing more comparisons. Most of the effort in analyzing sorting algorithms based on comparisons counts only comparisons for a few reasons:

• It is very general (machine independent)
• For most algorithms in that class, a reasonable implementation can "charge" every other operation to a comparison in a way that each comparison gets $O(1)$ operations

This second part is where your first try fell down. Hope this helps.

Even more

Everything so far was still theory. Practical sorting algorithms actually need to be tried on real machines. This is a whole area, and my understanding is that the current champ is not one of the standard algorithms, but something called "timsort", which you can find here http://svn.python.org/projects/python/trunk/Objects/listsort.txt

• Thank u very much Louis for ur explanation!...it is more clear now ! – forrestGump Apr 20 '12 at 11:35

The problem is that the analysis of Quicksort, as you have implemented it, assumes that accessing any element can be done at a constant cost, i.e. in $\mathcal O(1)$. This is not the case with linked lists.

Note that at the top of the while (right > left) { loop in your code, you cycle through all the elements until left and then repeatedly cycle through all the elements adjusting right. While in Quicksort this should just cost at most $\mathcal O(n)$, in your case it costs at most $\mathcal O(N^2)$, where $n$ is the current level of recursion and $N$ is the total number of elements.

As Louis pointed out in the comments below, there is a linked list analogue of Quicksort, but it needs to be implemented quite differently from what you did.

The bottom line: Linked lists are not arrays, and algorithms that will work well on arrays will not necessarily work well on linked lists. There are several good books on algorithms out there that will point you to good algorithms for each case.

Update

The code in the question has now been modified to reflect the implementation described by Louis below. There are still potential inefficiencies, however, in the selection of the pivot. In essence, any single operation inside the main loop which is not $\mathcal O(1)$ will mess-up the asymptotic behavior.

Oh, and creating new lists in every level of recursion is probably not extremely efficient either.

• I can't really see why this is, in general. You can just pick the pivot in $O(n)$ time and then accumulate the smaller and larger elements into two auxiliary lists, again in $O(n)$ time. This gives the usual asymptotics for quicksort. For example: haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell – Louis Apr 19 '12 at 13:23
• @Louis: Yes, but that's not what this user is doing. I've amended my reply to make that clearer though. Thanks for the input! – Pedro Apr 19 '12 at 13:24
• I see. By the time I saw it, whatever code was there had been deleted. Maybe editing the question is worthwhile. – Louis Apr 19 '12 at 15:25
• I have written the code in more easy and clear way.... – forrestGump Apr 20 '12 at 7:08
• @forrestGump How have you implemented addNode? And how are you picking the pivot? These things will all affect the speed. – Louis Apr 20 '12 at 7:48

The simplest way to sort lists is mergesort: Split the list into halves (just zip down, one element left, one right), sort left and right recursively, then merge (take the smaller of the first elements of the left and right lists). Well suited to lists (just linear transversals, mostly pointer juggling), and $\Theta(n \log n)$.