The common wisdom says that for small enough arrays insertion sort is the best. E.g., Timsort uses (binary) insertion sort for arrays up to 64 elements; from Wikipedia:
Some divide-and-conquer algorithms such as quicksort and mergesort sort by recursively dividing the list into smaller sublists which are then sorted. A useful optimization in practice for these algorithms is to use insertion sort for sorting small sublists, as insertion sort outperforms these more complex algorithms. The size of list for which insertion sort has the advantage varies by environment and implementation, but is typically between eight and twenty elements.
Is this actually correct? Are there any better alternatives?
In case this depends significantly on platform, I am most interested in .NET.
Yes, this is what I've learned in my algorithms classes, and this is also how sort is implemented in the C++ STL. From Wikipedia:
The June 2000 SGI C++ Standard
Template Library stl_algo.h
implementation of unstable sort uses
the Musser introsort approach with the
recursion depth to switch to heapsort
passed as a parameter, median-of-3
pivot selection and the Sedgewick
final insertion sort pass. The element
threshold for switching to the simple
insertion sort was 16.
I did some informal performance tests last year and C++ STL std::sort was about twice as fast as Array.Sort in .NET. I don't know how .NET Array.Sort is implemented, but in .NET, an access in an array requires a bounds check, unlike in C++, which could largely account for the performance difference.
I've found it really depends on how much work the comparison function has to do. Like if I'm indirectly sorting rows of a worksheet, and each comparison involves fetching a row and then comparing possibly several columns, possibly mixing numeric and string compares, it can get slow.
On the other hand, if the length of the array is short, it depends on how many times per second you need to sort it, because even if it is relatively slow compared to what it could be, you may never notice the difference.
If I have any doubt, I just code up a merge sort and go with that. I've had bad experience with qsort not being stable and sometimes taking a long time. Hand-coded merge sort is simple, dependable, and fast enough.
There are no faster O(n log n) algorithms than insertion sort for small lists. However, there are some O(n^2) algorithms that do compete. Notably, selection sort is not one of these, although it is good under the rare situation where swaps and moves are expensive. Bubble sort and variants are also just plain bad.
Network sort: A sorting algorithm, always stable, no branches. It has terrible specs overall, but no branches means stellar performance on the tiniest of lists. The base case is: if(a<b) swap(a,b);
Insertion sort with batches: On each loop, sort 2-4 elements, then insert them together. This reduces the number of moves and compares by 25 to 37 percent for longer lists. The overall effect is optimization for lists in the size range 16 to 64.
Since .NET is a language which doesn't compile to raw machinecode. I'd say calling an API function (which does use native code) probably is the fastest way to go
