Radix Sort – Why It Isn’t Used More Often

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.

I would speculate that:

• Array.sort is implemented as quicksort, because quicksort can sort anything in decent time given a comparator.
• Sorting a list of 10000 entries is not so common. Accessing a data-structure of 10000 or more elements is rather common. If you need to maintain order, a balanced search tree is often a better way to go than to sort your whole array every time you need the smallest element.
• Sorting primitives is not so common, despite what university may teach.

The point is, it's not such a common use case, that it's optimization needs to be in the standard library. If you have written an application, that has performance issues, where you determine through profiling that sorting an array of 10000+ ints is actually the bottleneck, then you might as well write the sorting by hand or reconsider your choice of data structure in the first place.