Deterministic selection

The idea is to find a pivot that is guaranteed to be near the middle without already knowing the median. Split the array into groups of five, find the median of each group, then recursively find the median of those medians. Use that as the pivot for ordinary partitioning.

Because the pivot is the median of the group medians, a constant fraction of the elements are provably smaller and a constant fraction provably larger, so quickselect can no longer be stuck with a lopsided split.

1static int select(int[] a, int lo, int hi, int idx) {         // idx is a 0-based sorted index
2    while (true) {
3        if (hi - lo < 5) { Arrays.sort(a, lo, hi + 1); return a[idx]; }
4        int groups = (hi - lo + 5) / 5;
5        for (int g = 0; g < groups; g++) {                      // median of each group of five
6            int gl = lo + g * 5, gr = Math.min(gl + 4, hi);
7            Arrays.sort(a, gl, gr + 1);
8            swap(a, lo + g, gl + (gr - gl) / 2);                // collect medians at the front
9        }
10        int pivot = select(a, lo, lo + groups - 1, lo + (groups - 1) / 2);   // median of medians
11        int p = partitionAroundValue(a, lo, hi, pivot);
12        if (idx == p) return a[p];
13        if (idx < p) hi = p - 1; else lo = p + 1;
14    }
15}

Worked example with 15 values: [9, 4, 7, 1, 8 | 15, 12, 6, 20, 3 | 11, 2, 18, 5, 14]. Sort each group of five and take its middle value. The medians are 7, 12 and 11, and the median of those three is 11, which becomes the pivot.

Partitioning around 11 puts nine values below it (9, 4, 7, 1, 8, 6, 3, 2, 5), the pivot itself, and five above (15, 12, 20, 18, 14). The pivot has rank 10 of 15, fairly central, as promised.

Finding the group medians costs O(n): sorting a group of five takes a constant number of steps. The recursive call on the n/5 medians costs T(n/5). Partitioning costs O(n). The recursive call on the remaining side costs at most T(7n/10), as shown in the next section.

T(n) ≤ T(n/5) + T(7n/10) + c·n. Since 1/5 + 7/10 = 9/10 < 1, the total work shrinks by a constant factor each level and the solution is T(n) = O(n). Using groups of three gives 1/3 + 2/3 = 1, which only solves to O(n log n).

Why is the pivot central? Half of the ⌈n/5⌉ group medians are less than or equal to the pivot. Each such median brings the two smaller members of its group along, so at least 3 · ⌈n/10⌉ ≈ 3n/10 elements are less than or equal to the pivot. By symmetry, at least 3n/10 are greater than or equal to it.

So after partitioning, each side has at most 7n/10 elements, plus a small constant for rounding. This is the bound the recurrence uses. Correctness itself is ordinary quickselect: whichever pivot is chosen, the answer lies on the side containing the target index.