Как работает QuickSort?

QuickSort — divide and conquer, in-place, average O(n log n), worst O(n²). Выбираем pivot, partition (меньше слева, больше справа), рекурсивно сортируем части.

def quicksort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

Выбор pivot критичен: последний элемент → worst case O(n²) на отсортированном; random pivot → expected O(n log n); median of medians → guaranteed O(n). Не stable, но cache-friendly, быстрее merge sort на практике. Introsort (C++ std::sort) — гибрид quicksort + heapsort для защиты от worst case.