Hacker News Reader

if you have decent (randomized) pivoting, you never hit the worst case or anything like it

You don't need randomized pivoting for this, there are deterministic ones like median of median that will also result in a O(nlogn) worst case.

Also note that with a randomized pivoting you _might_ hit a O(n^2) worst case, it's just that it's incredibly rare and cannot be forced by an attacker controlling your input, so for most practical purposes can be ignored.

median of median does give you guarenteed n*log(n) but it doubles your memory reads per pass making it pretty poor. single random is almost guarenteed to take fewer passes (and median of 3-7 random values can make the number of extra passes over the minimum to be very low)

You don't have to use median of medians for every pass, you can use it only when you detect that each pass is not making enough progress, i.e. when you hit the worst case.

Reply on news.ycombinator.com