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.
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: