Deterministic Select

It is interesting to note that there is a way to get rid of the randomness here without losing the nice linear running time bound. After all, the worst-case running time here is O(n²), whereas we know we can do it in $O(n \log n)$ deterministically.

The resulting algorithm is not really practical, but it's clever.

Idea: Replace with choice of pivot element with something that guarantees we get a sufficiently good split.

• Step 1: Break n elements into blocks of 5 each.
• Step 2: Compute the median of each 5-element block in constant time.
• Step 3: Collect together the n/5 medians and recursively compute their median.
• Step 4: Chose the resulting element as a pivot.