sort(list); return list[nth];

This is easy to code but runs a little slow, in .

For something fast, there’s an algorithm that runs in expected called QuickSelect (Wikipedia), a cross between Quicksort and binary search. Like Quicksort, there’s a worst-case time of , so where handling large user-supplied inputs consider choosing the partition pivot element randomly.

**The gist**:

function quickselect(list, nth) begin = 0, end = list.size() loop partition list[begin, end) if partition equals nth, return list[partition] else drill down on partition's appropriate side loop end

My implementation is in git and below:

Continue reading