Одинаковая асимптотика, разные времена

Quicksort и merge sort оба имеют сложность O(n log n) в среднем. По «академической» оценке они эквивалентны. Но на реальных данных и реальных процессорах quicksort часто работает быстрее в 1.5-3 раза.

Этот урок — про константу под асимптотикой: что именно делает разницу, и почему cache locality и in-place свойства имеют значение.

Где находятся данные при сортировке

Напомним из модуля 3 иерархию памяти:

Чем выше — тем быстрее, но тем меньше. На уровне L1 операция мгновенная, на уровне RAM она «уже секунда» (по меркам CPU). Идея cache locality: держать «горячие» данные в L1/L2, избегать random access к RAM.

Сортировка миллиона int (4-8 МБ) не помещается в L1 и L2, но влезает в L3. Cache hit/miss решающе влияют на скорость.

Quicksort: sequential access в partition

В quicksort partition — это один проход по массиву слева направо с двумя указателями. Каждый шаг — линейное чтение arr[j]. Prefetcher идеально работает: знает, что следующая cache line будет нужна, подгружает её заранее.

В пиковом случае partition обрабатывает 8 int64 за один cache line, без cache miss между ними.

После partition мы рекурсируем в две половины. На каждой следующей рекурсии массив становится меньше — в какой-то момент он целиком влезает в L1 cache (массив <= 8000 int = 32 КБ). С этого момента вся работа происходит «в L1», а это в 100 раз быстрее RAM.

Merge sort: pointer chasing в merge

Merge функция работает с двумя разными массивами: left и right. Указатели i и j указывают в разные участки памяти. Plus мы записываем в третий массив result.

Это три параллельных потока чтения/записи. Prefetcher может справляться, но cache hit rate ниже, чем у one-stream sequential read.

Ещё хуже: на нижнем уровне рекурсии merge sort создаёт много маленьких массивов через срезы arr[:mid] и arr[mid:]. Каждый срез — это allocation, копия и cleanup. На Python это особенно дорого (PyList allocation).

In-place vs out-of-place

Quicksort работает in-place: дополнительная память — только стек рекурсии O(log n). Это ~10-50 КБ на стек для миллиона элементов.

Merge sort требует O(n) дополнительной памяти. Для 10М int это 80 МБ временной памяти. Это:

1. Allocation — операция allocate+initialize O(n) — не бесплатная.
2. Cache pressure — рабочие данные занимают больше L3, происходит больше cache miss.
3. Memory bandwidth — копирование туда-обратно потребляет полосу пропускания памяти.

В Python разница ещё больше: каждый промежуточный list — это PyListObject с overhead 56+ байт, плюс reference counts. На 10М int временные allocations могут добавить 100+ МБ временной памяти.

Реальный бенчмарк

Сравним собственные реализации на 10М int:

import random
import time

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = lomuto_partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

def lomuto_partition(arr, lo, hi):
    # с защитой через random pivot
    rand_idx = random.randint(lo, hi)
    arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
    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

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result

random.seed(42)
import sys
sys.setrecursionlimit(50000)
N = 1_000_000
arr = [random.randint(0, 10**9) for _ in range(N)]

a = arr[:]
t = time.perf_counter(); quicksort(a); print("quicksort:", time.perf_counter() - t, "s")

a = arr[:]
t = time.perf_counter(); merge_sort(a); print("merge_sort:", time.perf_counter() - t, "s")

a = arr[:]
t = time.perf_counter(); sorted(a); print("Timsort:", time.perf_counter() - t, "s")

Типичный вывод (на M-серии 2024 ноутбуке):

quicksort:  4.2 s
merge_sort: 6.8 s
Timsort:    0.3 s

Quicksort быстрее merge_sort в 1.6 раза — несмотря на одинаковую асимптотику. Timsort (на C, оптимизированный) — в 20 раз быстрее обоих чистых Python-реализаций.

Та же история на C++

// std::sort обычно introsort (quicksort + heapsort)
std::sort(v.begin(), v.end());

// std::stable_sort обычно merge sort
std::stable_sort(v.begin(), v.end());

На 10М int на x86_64:

• std::sort: ~500 мс,
• std::stable_sort: ~700-900 мс.

Разница меньше, чем в Python, но в той же сторону. И главное — stable_sort требует O(n) extra memory, что иногда критично.

Когда merge sort всё-таки выбирают

1. Стабильность важна. Sort by name, потом by age — нужен stable. Quicksort не подходит.
2. External sort. Файл больше RAM — нужен merge sort, работающий с потоками.
3. Параллельная сортировка. Merge sort легче параллелится, чем quicksort.
4. Гарантия worst-case. Без introsort’а quicksort может выродиться в O(n^2). Если требование «никаких deg-cases», merge sort гарантирует O(n log n).
5. Linked list. На связном списке merge sort работает за O(n log n) без дополнительной памяти (используя in-place merge). Quicksort на linked list работает плохо — нет random access.

Когда quicksort оптимален

1. In-memory sort на массиве. Главный сценарий.
2. Жёсткие требования к памяти. Embedded, real-time, где O(n) extra unacceptable.
3. Уже в кэше. Маленькие массивы (10к-100к элементов).
4. Random access структура. Array, vector, dynamic array.

Что делает Timsort

Timsort — гибрид, который пытается совместить плюсы обоих:

• Использует merge sort как базу (stable, гарантированно O(n log n)),
• Использует insertion sort на коротких runs (cache-friendly, near-linear на отсортированном),
• Adaptive: распознаёт уже-отсортированные сегменты и не сортирует их повторно.

Это даёт в среднем скорости quicksort с гарантией O(n log n) и stability. Поэтому Python’s list.sort() и Java’s Arrays.sort() для объектов используют Timsort.

Подробно — в уроке 14.01.

DE-кейс: сортировка широкой таблицы

Сценарий: pandas DataFrame, 10М строк, 20 колонок. df.sort_values("ts").

Что делает pandas:

1. Использует Timsort (через numpy).
2. Не перемещает строки — сначала строит permutation array (массив индексов), потом применяет к каждой колонке.

Это важно: для широкой таблицы прямая сортировка требует переноса всех 20 значений на каждый swap. Permutation подход разделяет: сначала разобраться, какой строке какой порядок, потом применить — в одно касание per row.

Memory cost: O(n) для permutation array (8 байт на int64-индекс). Это 80 МБ для 10М строк — но это намного дешевле, чем повторное копирование данных при каждом swap.

Тот же приём используется в Arrow, Parquet и многих DataFrame-движках.

DE-кейс: сортировка blob’ов (большие строки)

Сценарий: массив из 1М строк длиной 1-10 КБ каждая. Размер ~1-10 ГБ.

Прямая sorted() с lambda key=lambda s: … = в худшем случае O(n log n) сравнений, каждое сравнение O(length) — итого O(n log n * avg_length). На 1М строк — миллиарды операций.

Оптимизация: decoration или sort by key.

# плохо
sorted(strings, key=lambda s: s[:50])    # каждый вызов делает срез

# хорошо
sorted([(s[:50], s) for s in strings])   # ключ вычисляется один раз

Или использовать key=, тогда sorted кеширует ключи:

sorted(strings, key=lambda s: s[:50])   # на самом деле — Python кэширует

Тут уже без копий. Но в случае с большими структурами decoration-undecoration паттерн (Schwartzian transform) даёт лучший контроль.

Попробуй сам

Возьмите три массива по 1М int:

1. random,
2. sorted,
3. reverse-sorted.

Для каждого замерьте:

• sorted(arr) (Timsort),
• ваш quicksort (с random pivot для защиты),
• ваш merge_sort.

Ожидаемые результаты:

Timsort даёт огромную скидку на отсортированных данных — он их обнаруживает и обрабатывает за O(n). Quicksort и merge sort на каждой форме делают O(n log n) операций. Quicksort быстрее merge примерно в 1.5x за счёт in-place и cache.

В следующем уроке — еще один тип сортировок: counting и radix. Они работают вне модели сравнений и могут давать O(n) при специальных условиях.