3 ms·
Well, nobody really uses plain quicksort in practice (maybe libc qsort?), but a lot of practical fast sort algorithms are variant (or based on) quicksort (inclu
by gpderetta 7y ago
Well, nobody really uses plain quicksort in practice (maybe libc qsort?), but a lot of practical fast sort algorithms are variant (or based on) quicksort (including the ips4o you linked to if I'm reading the paper correctly).
A better claim would be that, among the comparison based sorts, algos in the quicksort family tend to be faster in practice.
- lorenzhs 7y agoYeah, my implicit comparison was to something like std::sort from GNU's libstdc++, which is introsort, a quicksort-insertionsort-hybrid. Plain quicksort is indeed not great. ips4o is a samplesort-derivative (the name stands for Inplace Super-Scalar Sample SOrt), which is kinda quicksort-derived, but doesn't use one pivot, but many (in the case of ips4o, 255, iirc). It's heritage traces back to quicksort, if you will, but it's also very different.