def nth_element(seq_in, n, key=lambda x: x):
    start, end = 0, len(seq_in)
seq = [(x, key(x)) for x in seq_in]

def partition_pred(x):
    return x[1] < seq[end - 1][1]
while start != end:
    pivot = (end + start) // 2
seq[pivot], seq[end - 1] = seq[end - 1], seq[pivot]
pivot = partition(seq, partition_pred, start, end)
seq[pivot], seq[end - 1] = seq[end - 1], seq[pivot]
if pivot == n:
    break
if pivot < n:
    start = pivot + 1
else:
    end = pivot
seq_in[:] = (x for x, k in seq)
Fast way to get N Min or Max elements from a list in Python