Hacker News Reader

That's still a quicksort - it always has n^2 as its worst case I thought? If you pick the wrong pivot each time.

There are ways to make the n^2 worst case extraordinarily unlikely, and there is a way to make it impossible (though it is highly technical).

Some others have posted methods (random pivot, median of 3). The gnu libc qsort implementation is a good learning tool (it uses median of 3). I think CLRS has the guaranteed n log n version.

> That's still a quicksort - it always has n^2 as its worst case I thought? If you pick the wrong pivot each time.

Pick median of three random elements as pivot; it's hard to pick wrong pivot every time unless your RNG always returns 7.

Why three random elements though? If you expect some structure in the array, then picking pivots based on that structure makes more sense (e.g. first, middle and last for sorted, reverse sorted for partially sorted arrays).

On the other hand, if you are sorting unsanitised input, then random is good, but it should be secure pseudo-random numbers if it's important to your security/performance whilst under attack.

Reply on news.ycombinator.com