Hacker News new | comments | show | ask | jobs | submit login

> You can also make quicksort worst-case complexity to be nlogn.

Quicksort in the worst take can take O(n^2) time, not O(nlogn).

If one takes the time to select optimal pivots it becomes O(nlogn). The selection is free from a big-O perspective, because it's O(n) immediately before the O(n) list division step.

Of course, nobody does this, because the selection is not really free. The constant factor cost of choosing the optimal pivot hurts the average case, making the modified quicksort tend to do worse than heapsort or introsort.

You can use a randomized selection algorithm to find the median in linear time, and if you use the median as a pivot you will never get worst case n^2 behavior.

This is not used in practice because the probability of getting worst case behavior is extremely slim if you do some clever, and cheap, tricks.

Randomized selection algoritm is actually O(N^2) in the worst case. Median of medians is the O(N) worst case selection algorithm.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact