Quickselect: One Order Statistic in O(n)

Quickselect answers "what is the k-th smallest element?" without sorting anything. It borrows one move from quicksort — partition: pick a pivot, shuffle the array so everything smaller sits to its left and everything larger to its right. After that one pass, the pivot occupies its final sorted position.

Now the trick that makes it faster than quicksort: check which side of the pivot index k falls on, and throw the other side away entirely. Recurse only into the surviving half. The work shrinks: n + n/2 + n/4 + ... which totals about 2n — O(n) average time, versus O(n log n) for a full sort.

What to watch for:

• The pivot is chosen at random. A fixed pivot (always first or last) hits O(n squared) on already-sorted input — randomizing is not optional.
• After each partition, the pivot drops into its slot with its final index label. That index is the only fully-decided position.
• Watch the discarded half collapse off-screen. Nothing in it is ever touched again — that is the entire speed advantage.
• The surviving range shrinks toward a single glowing bar: the answer, found without the rest ever reaching sorted order.