Быстрая сортировка (quicksort)

Быстрая сортировка выбирает опорный элемент (pivot), разбивает массив на меньшие и большие, затем рекурсивно сортирует обе части. Быстра на практике благодаря хорошей работе с кешем.

Сложность: время O(n log n) в среднем, O(n^2) в худшем случае при неудачном выборе pivot (рандомизация снижает риск). Память: O(log n) на стек рекурсии. Обычно неустойчива.

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left  = [x for x in a if x < pivot]
    mid   = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quicksort(left) + mid + quicksort(right)