3 ms·
There are sorting methods faster than quicksort though. O(n loglog n) for instance. Or for randomized its O(n sqrt log log n).
by ultrablack 6y ago
There are sorting methods faster than quicksort though. O(n loglog n) for instance. Or for randomized its O(n sqrt log log n).
- ogogmad 6y agoOmega(n log n) is the fastest possible for a comparison sort, by a simple decision tree argument. This is true even for the average case. Their algorithm is a comparison sort, as they make clear on page 5.
- deleted 6y ago[deleted]