C++ – What sorting algorithm does STL use

As deterministic as computers themselves are, computer engineering is not an exact science. Two people, given the same problem domain, will perform an analysis and develop two different solutions that satisfy all constraints of the problem. It may be difficult or impossible to empirically determine which of these is "better" in the general case.

My guess is that the .NET QuickSort is layered on top of something in the MFCs or Windows API, and is probably inherited from much older versions of Windows where the multi-threadable advantage of MergeSort wouldn't have even been considered for the computers of the day. (EDIT: it's not, though Microsoft developers have been QuickSort fanboys for a long time, as evidenced by this choice of sorting implementation since MS-DOS).

Java, which can't use any platform-specific implementation because Java was designed from scratch to be completely platform-independent, went a different way. Who knows why MergeSort came out on top; my wild guess is that the implementation won some sort of performance competition versus some other sorts the developers came up with, or else that an O(n)-space MergeSort just looked best on paper in terms of best-case and worst-case performance (MergeSort has no Achilles' heel relating to element selection like QuickSort, and its best-case is a near-sorted list while that's often QuickSort's worst). I doubt multithreading benefits were initially considered, but the current implementation may well be multithreaded.

The problem with Data.List.sort is that it uses merge sort, which creates new lists during each pass. So a lot of time is spent on allocating and freeing memory.

Surprisingly, AFAIK there isn't a sorting library for mutable arrays, which are likely to be faster. So I tried to make one and put it on github: marray-sort. It needs rigorous testing, polishing and optimizing too, but so far it already seems to be significantly faster than Data.List.sort.

If you make any experiments with it, I'd be happy to see the results. I put your (slightly modified) benchmark to src-test/Test.hs for convenience. Don't forget to compile everything with -O2 to trigger the necessary compiler optimizations.

Edit: I found out now that there is an implementation if introsort for mutable vectors in vector-algorithms. According to my measurements, it is slightly faster (5-10%) than my attempt above for MArrays See also: How does one sort with Data.Vector.Generic.Mutable?.