3 ms·
See "median of medians algorithm": https://en.wikipedia.org/wiki/Median_of_medians https://en.wikipedia.org/wiki/Median_of_medians It's hairier than a partial
by username223 10y ago
See "median of medians algorithm": https://en.wikipedia.org/wiki/Median_of_medians https://en.wikipedia.org/wiki/Median_of_medians
It's hairier than a partial quicksort, but (if you erase the proof and weigh the chalk dust) guaranteed linear time.
- gpderetta 10y agoand median of medians can be used to implement quicksort with O(NlogN) worst case. It is usually not worth it as other hybrid quicksorts like introsort are faster in practice. On an unrelated note, I was once asked to prove the upper bound for median of median on an interview...