Fast stable sort for small arrays (under 32 or 64 elements)

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.