Hacker News Reader

+1. My favourite bit is when pivots are chosen randomly in quicksort, we get linearithmic expected complexity. The CLRS proof using indicator random vars was a oh-shit moment.

View on HN

Btw, you can make quicksort deterministically O(n log n) if you pick the pivot point with linear median search algorithm. It's impressive how randomness lets you pick a balanced pivot, but even more impressive that you could do the same without randomness.

Similarly, quickselect with random pivots runs in expected linear time.

For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycoding...

Reply on news.ycombinator.com