Because in the real world, where all our code must actually run, quicksort beats practically every other algorithm on the vast majority of inputs. Its cache be

Because in the real world, where all our code must actually run, quicksort beats practically every other algorithm on the vast majority of inputs. Its cache behavior is better than heap sort, its memory usage is lower than merge sort, and even its O(log n) memory usage is efficiently allocated on the stack as opposed to hitting a slow system allocator. "Engineering a Sort Function"[0] covers this quite well. In some experiments of my own, I've found that even Smoothsort[1] (an algorithm specifically designed to have a smooth transition from linear to linearithmic behavior on nearly-sorted input) can't beat the C++ system's introsort (a quicksort variation with a fallback to heapsort) in already-sorted inputs. [0] http://www.skidmore.edu/~meckmann/2009Spring/cs206/papers/spe862jb.pdf http://www.skidmore.edu/~meckmann/2009Spring/cs206/papers/sp... [1] http://www.keithschwarz.com/smoothsort/ http://www.keithschwarz.com/smoothsort/