Quick select

Partition — one side recurse.

Try this in Python

import random

def quickselect(a, k):
    pivot = random.choice(a)
    lows = [x for x in a if x < pivot]
    highs = [x for x in a if x > pivot]
    mids = [x for x in a if x == pivot]
    if k < len(lows):
        return quickselect(lows, k)
    if k < len(lows) + len(mids):
        return pivot
    return quickselect(highs, k - len(lows) - len(mids))

print(quickselect([9, 8, 7, 6, 5, 4], 2))

Key takeaways

• Worst-case pivots.
• nsmall small k.
• Three-way partition dupes.