4 ms·
It's not even the fastest comparison-based sorter for the vast majority of inputs. There are much faster sorters out there that exploit the details of modern ha
by lorenzhs 7y ago
It's not even the fastest comparison-based sorter for the vast majority of inputs. There are much faster sorters out there that exploit the details of modern hardware (branch prediction is a big one, parallelism is also an obvious win if you can make use of it, etc), e.g. https://github.com/SaschaWitt/ips4o/ https://github.com/SaschaWitt/ips4o/ (sequential and parallel, disclaimer: the authors are my colleagues) or https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort (sequential)
- gpderetta 7y agoWell, 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.