Как отсортировать данные, которые не помещаются в память (внешняя сортировка)

Внешняя сортировка режет данные на куски размером с доступную память, сортирует каждый и пишет на диск, а затем сливает отсортированные прогоны k-путевым слиянием через min-кучу.

Две фазы

1. Формирование прогонов: читаем M байт, сортируем в памяти, пишем файл. Получаем ⌈N/M⌉ прогонов.
2. k-путевое слияние: куча из «голов» всех прогонов, каждый читается своим буфером. Одна операция — O(log k).

Пример: 1 ТБ при 8 ГБ памяти — около 125 прогонов, которые сливаются за один проход с буферами по ~64 МБ.

В Python вторую фазу даёт heapq.merge(*files) — ленивое слияние уже отсортированных итераторов.

Что влияет на скорость

• Узкое место — диск: число проходов 1 + ⌈log_k(N/M)⌉, поэтому k делают большим, а чтение — крупными последовательными блоками.
• Replacement selection на куче даёт прогоны в среднем длиной 2M на случайных данных.

Где встречается

GNU sort -S 2G --parallel=8, СУБД (в EXPLAIN ANALYZE PostgreSQL — external merge, когда не хватило work_mem), shuffle в MapReduce и Spark.

Коротко для собеседования

Большой файл сортируют по частям: каждый кусок, влезающий в память, сортируют и сбрасывают на диск, а потом все куски сливают через кучу. Узкое место — диск, поэтому проходов делают меньше за счёт большого k и крупных буферов, а при нехватке дескрипторов сливают группами.