Why is Insertion sort better than Quick sort for small list of elements?

Solution 1:

Big-O Notation describes the limiting behavior when n is large, also known as asymptotic behavior. This is an approximation. (See http://en.wikipedia.org/wiki/Big_O_notation)

Insertion sort is faster for small n because Quick Sort has extra overhead from the recursive function calls. Insertion sort is also more stable than Quick sort and requires less memory.

This question describes some further benefits of insertion sort. ( Is there ever a good reason to use Insertion Sort? )

Solution 2:

Define "small".

When benchmarking sorting algorithms, I found out that switching from quicksort to insertion sort - despite what everybody was saying - actually hurts performance (recursive quicksort in C) for arrays larger than 4 elements. And those arrays can be sorted with a size-dependent optimal sorting algorithm.

That being said, always keep in mind that O(n...) only is the number of comparisons (in this specific case), not the speed of the algorithm. The speed depends on the implementation, e. g., if your quicksort function as or not recursive and how quickly function calls are dealt with.

Last but not least, big oh notation is only an upper bound.

If algorithm A requires 10000 n log n comparions and algorithm B requires 10 n ^ 2, the first is O(n log n) and the second is O(n ^ 2). Nevertheless, the second will (probably) be faster.

Solution 3:

O()-notation is typically used to characterize performance for large problems, while deliberately ignoring constant factors and additive offsets to performance.

This is important because constant factors and overhead can vary greatly between processors and between implementations: the performance you get for a single-threaded Basic program on a 6502 machine will be very different from the same algorithm implemented as a C program running on an Intel i7-class processor. Note that implementation optimization is also a factor: attention to detail can often get you a major performance boost, even if all other factors are the same!

However, the constant factor and overhead are still important. If your application ensures that N never gets very large, the asymptotic behavior of O(N^2) vs. O(N log N) doesn't come into play.

Insertion sort is simple and, for small lists, it is generally faster than a comparably implemented quicksort or mergesort. That is why a practical sort implementation will generally fall back on something like insertion sort for the "base case", instead of recursing all the way down to single elements.