Как работает quickselect и почему O(n)?

Quickselect (Hoare's algorithm) — найти k-й элемент за average O(n), worst O(n²). Как quicksort, но рекурсивно только в одну половину.

import random
def quickselect(arr, k):   # kth smallest (0-indexed)
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    lows = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]
    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

Почему O(n): на каждом уровне O(n) для partition, но рекурсия только в одну половину → n + n/2 + n/4 + ... = O(2n) = O(n). Worst case (pivot всегда max/min) → O(n²). Median of medians (Blum) — guaranteed O(n), но выше константный фактор. В C++ — std::nth_element.