Further improvements to quicksort implementation of qsort

[statham-arm]

llvm-libc's qsort, the Quicksort version, works but is not especially polished.

In a recent PR (#110849) @michaelrj-google observed that more of the functions in the quicksort headers should be marked with LIBC_INLINE, so that the top-level qsort function doesn't incur any internal function-call overheads except when actually recursing.

It might also be worth considering other standard optimizations commonly used in quicksort algorithms (after benchmarking to make sure they really are improvements):

• make sure we have the best choice of partitioning strategy. Currently we always pick the element in the middle, which at least behaves reasonably if the input list is already mostly sorted (better than picking the start or end element). But median of (start, middle, end) is a common choice; maybe that's better?
• consider not recursing right down to lists of size 2, but instead, stop when every remaining sublist has size at most 8 or 16 or something like that, and then finish up with a pass of insertion sort
• adopt "introsort", a variation of quicksort in which you detect when your sublists aren't getting smaller fast enough, and switch over to heapsort. That way you still keep most of quicksort's good constant factor, but remove the quadratic-time worst case, because that's the case where heapsort takes over.

[Rajveer100]

I think adding randomness would be a nice choice. We can pick a random index during the partition and then swap it with the end element, the probability of a good complexity would be pretty high, i.e, close to its best case.

Yeah, at this point intro sort is pretty much used everywhere in most standard libraries, I did see tim sort in some cases too.

What do you think of dual-pivot though?

[statham-arm]

Dual pivot is outside my experience, I'm afraid.

One downside of random pivot selection is that it can affect the output order, in the presence of elements whose keys compare equal. Quicksort is already not stable – it won't guarantee to leave equal-keyed elements in their original order – but it seems particularly bad if it doesn't even leave them in a deterministic order if you run exactly the same sort twice. You could imagine that breaking repeatability of some test case you were debugging, for example.

[Rajveer100]

It's about the chances, it's less predictable to have a really bad case.

For making it stable we could use additional O(n) space by pairing elements, like (x, i).

[llvmbot]

@llvm/issue-subscribers-libc

Author: Simon Tatham (statham-arm)

llvm-libc's `qsort`, the Quicksort version, works but is not especially polished. In a recent PR (#110849) @michaelrj-google [observed](https://github.com/llvm/llvm-project/pull/110849#pullrequestreview-2352848252) that more of the functions in the quicksort headers should be marked with `LIBC_INLINE`, so that the top-level `qsort` function doesn't incur any internal function-call overheads _except_ when actually recursing. It might also be worth considering other standard optimizations commonly used in quicksort algorithms (after benchmarking to make sure they really are improvements): * make sure we have the best choice of partitioning strategy. Currently we always pick the element in the middle, which at least behaves reasonably if the input list is already mostly sorted (better than picking the start or end element). But median of (start, middle, end) is a common choice; maybe that's better? * consider not recursing right down to lists of size 2, but instead, stop when every remaining sublist has size at most 8 or 16 or something like that, and then finish up with a pass of insertion sort * adopt "introsort", a variation of quicksort in which you detect when your sublists aren't getting smaller fast enough, and switch over to heapsort. That way you still keep most of quicksort's good constant factor, but remove the quadratic-time worst case, because that's the case where heapsort takes over.