Average time complexity of quicksort vs insertion sort

Question

I'm lead to believe that quick sort should be faster than insertion sort on a medium size unorderd int array. I've implemented both algorithms in java and I notice quicksort is significantly slower then insertion sorrt.

I have a theory: quiksort is being slower because it's recursive and the call it's making to it's own method signature is quite slow in the JVM which is why my timer is giving much higher readings than I expected, whereas insertion isn't recursive and all thwe work is done within one method so they JVM isn't having to do any extra grunt work? amirite?

Answer 1

You may be interested in these Sorting Algorithm Animations.

Answer 2

The fastest implementations of quicksort use looping instead of recursion. Recursion typically isn't very fast.

Answer 3

theoretically Quick Sort should work faster than insertion sort for random data of medium to large size.

I guess the differences should be in the way QS is implemented:

pivot selection for the given data ?(3-median is a better approach)

using the same Swap mechanism for QS and insertion sort ?

is the input random enuf, i.e ., if you have clusters of ordered data performance will
suffer.

I did this exercise in C and results are in accordance with theory.

Answer 4

Unless you've hit one of Quicksort's pathological cases (often, a list that is already sorted), Quicksort should be O(n log n) — substantially faster than insertion sort's O(n^2) as n increases.

You may want to use merge sort or heap sort instead; they don't have pathological cases. They are both O(n log n).

(When I did these long ago in C++, quicksort was faster than insertion sort with fairly small ns. Radix is notable faster with mid-size ns as well.)

Answer 5

You have to be careful how you make the recursive calls, and because it's Java, you can't rely on tail calls being optimized, so you should probably manage your own stack for the recursion.

Everything that is available to be known about quicksort vs insertion sort can be found in Bob Sedgewick's doctoral dissertation. The boiled-down version can be found in his algorithms textbooks.

Answer 6

I remember that in school, when we did sorting in Java, we would actually do a hybrid of the two. So for resursive algorithms like quicksort and mergesort, we would actually do insertion sort for segments that were very smal, say 10 records or so.

Recursion is slow, so use it with care. And as was noted before, if you can figure a way to implement the same algorithm in an iterative fashion, then do that.

Answer 7

There are three things to consider here. First, insertion sort is much faster (O(n) vs O(n log n)) than quicksort IF the data set is already sorted, or nearly so; second, if the data set is very small, the 'start up time" to set up the quicksort, find a pivot point and so on, dominates the rest; and third, Quicksort is a little subtle, you may want to re-read the code after a night's sleep.

Answer 8

How are you choosing your pivot in Quicksort? This simple fact is the key to your question, and probably why Quicksort is running slower. In cases like this it's a good idea to post at least the important sections of your code if you're looking for some real help.