Re:A Killer Adversary for Quicksort (1999) [pdf]
by taeric on Friday October 30, 2015 @01:31PM
(#10479194)
> We have already established that O(n log n) is the lower bound, and we have reached this lower bound. This is where big O stops being useful. A metric that compares equal for every relevant algorithm (mergesort, introsort, pdqsort, timsort, smoothsort, heapsort) is not a useful metric.
With the explosion of cores and special purpose hardware, it is interesting to think of how long before sorting network routines are more practical. Dropping the runtime to O(lg n) would be enticing. :)
With the explosion of cores and special purpose hardware, it is interesting to think of how long before sorting network routines are more practical. Dropping the runtime to O(lg n) would be enticing. :)