[matslina]

Glibc falls back to quicksort from merge sort (its default algorithm) when there's to little free memory available to accommodate merge sort's O(n) requirement. Quicksort only uses O(log n) additional memory, making it a good option in that sense. O(1) would of course be better, but even for huge inputs that logarithm makes the memory consumption a non-issue in most cases. Heapsort does give you O(1) memory, but also comes with poorer cache locality and overall performance than quicksort, making it a not so compelling option.