4 ms·
"Faster sorting"? Heap sort achieves the Gleason bound and, thus, is the fastest possible sort by comparing pairs of keys. For keys not too long, radix sort c
by graycat 3y ago
"Faster sorting"?
Heap sort achieves the Gleason bound and, thus, is the fastest possible sort by comparing pairs of keys.
For keys not too long, radix sort can be faster.
These facts have been very well known for decades.
There might be more to do in sorting with some different records, keys, computer architecture, concerns about caches and locality of reference, but otherwise, thankfully, sorting is a well solved problem.
- CyberDildonics 3y agoHeap sort gets beat by sorting algorithms with better locality. You can't be the fastest while skipping through memory for every operation.
- janwas 3y agoAgreed. And I am not aware of a heapsort that can take advantage of SIMD, so our not very well-tuned heapsort is about 20 times slower in practice than our VQSort (vectorized quicksort).
- CaptainNegative 3y agoHeap sort's worst- and average-case running time are both provably within a constant factor of optimality (both in running time and number of comparisons), but it's either likely or straight up provably not actually optimal in any of the four categories.