The k-th Order Statistic

To find a median or a percentile we don't need a sorted array, only one position. Quickselect partitions like quicksort but keeps only the side that holds position k: on [7, 10, 4, 3, 20, 15] it finds the third smallest, 7, in two passes and 9 comparisons. We see why the work n + n/2 + n/4 + ... is about 2n (measured: 2.76 n comparisons for the median of a million random values), how a fixed pivot on sorted input goes quadratic, and what std::nth_element guarantees, including measurements on this Mac: about 53 ms versus 657 ms for a full sort of 10^7 values, and a quadratic blow-up of libc++'s nth_element against an adversarial comparator.