Сортировки: быстрая и слиянием

Две сортировки за O(n log n), которые обязан знать каждый кандидат.

Divide and conquer («разделяй и властвуй») — стратегия: разбить задачу на части, решить каждую рекурсивно и объединить результаты.

Сортировка слиянием (merge sort)

Делим массив пополам, рекурсивно сортируем половины и сливаем два отсортированных массива в один. Слияние — линейный проход двумя указателями. Сложность всегда O(n log n), сортировка стабильная (сохраняет порядок равных элементов), но требует O(n) дополнительной памяти.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

print(merge_sort([5, 2, 8, 1, 9, 3]))
print(merge_sort([3, 3, 1, 1, 2, 2]))

Вывод:

[1, 2, 3, 5, 8, 9]
[1, 1, 2, 2, 3, 3]

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

Выбираем опорный элемент (pivot), разбиваем массив на «меньше», «равно» и «больше» pivot, рекурсивно сортируем крайние части. В среднем O(n log n), в худшем O(n^2) (на уже отсортированном при плохом выборе pivot).

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

print(quick_sort([5, 2, 8, 1, 9, 3]))
print(quick_sort([4, 4, 4, 1, 2]))

Вывод:

[1, 2, 3, 5, 8, 9]
[1, 2, 4, 4, 4]

Сравнение

Как работает под капотом

Глубина рекурсии у обеих — log n (массив делится пополам), и на каждом уровне выполняется O(n) работы (слияние или разбиение), отсюда O(n log n). Merge sort стабилен, потому что при равенстве берёт элемент из левой половины первым. Quick sort быстрее на практике из-за работы «на месте» и хорошей локальности кэша, но уязвим к худшему случаю — поэтому pivot выбирают случайно или по медиане трёх.

Частые ошибки

• В merge sort при равенстве брать из правой половины — теряется стабильность.
• Считать quick sort всегда O(n log n) — в худшем случае это O(n^2).
• Забыть базовый случай рекурсии (длина 0 или 1) — бесконечная рекурсия.

Итог

• Обе — divide and conquer со средним O(n log n).
• Merge sort: стабильна, гарантированный O(n log n), но O(n) памяти.
• Quick sort: на месте, в среднем быстрее, но худший случай O(n^2).