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