Algorithms Optimization – Big O(n log n) and Quicksort Operations

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 wouldn't agree that quicksort is better than other sorting algorithms in practice.

For most purposes, Timsort - the hybrid between mergesort/insertion sort which exploits the fact that the data you sort often starts out nearly sorted or reverse sorted.

The simplest quicksort (no random pivot) treats this potentially common case as O(N^2) (reducing to O(N lg N) with random pivots), while TimSort can handle these cases in O(N).

According to these benchmarks in C# comparing the built-in quicksort to TimSort, Timsort is significantly faster in the mostly sorted cases, and slightly faster in the random data case and TimSort gets better if the comparison function is particularly slow. I haven't repeated these benchmarks and would not be surprised if quicksort slightly beat TimSort for some combination of random data or if there is something quirky in C#'s builtin sort (based on quicksort) that is slowing it down. However, TimSort has distinct advantages when data may be partially sorted, and is roughly equal to quicksort in terms of speed when the data is not partially sorted.

TimSort also has an added bonus of being a stable sort, unlike quicksort. The only disadvantage of TimSort uses O(N) versus O(lg N) memory in the usual (fast) implementation.