.net - 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

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.