Quickselect: find the k-th smallest element in O(n), no sorting required

The previous article on binary search ended with a claim that probably raised an eyebrow: you can find the k-th smallest element in an unsorted array in O(n) average time, without sorting. If sorting is O(n log n), how does selection get away with O(n)? The answer is quickselect, and understanding it will permanently change how you think about the divide-and-conquer family. 1. The problem sorting solves that you didn't actually need to solve When you sort an array to find the k-th smallest eleme