Block Sort (WikiSort)

Проблема

Merge sort гарантирует устойчивость и O(n log n), но платит за это O(n) дополнительной памяти на слияние. Heap sort и quicksort экономят память, но теряют устойчивость (heap sort) или гарантию худшего случая (quicksort). Нужен способ слить два отсортированных участка массива друг с другом, оставаясь устойчивым, но не выделяя память, пропорциональную размеру всего массива.

Решение

Идея блочного слияния - переставлять сами элементы внутри массива вместо копирования в буфер. Простейший вариант: при слиянии двух участков [lo, mid) и [mid, hi), как только элемент из правого участка оказывается меньше текущего элемента левого, весь блок между ними сдвигается на одну позицию вправо (поворот подмассива), а меньший элемент занимает освободившееся место. Настоящий WikiSort идёт дальше и переставляет не отдельные элементы, а целые блоки размера ≈√n за один шаг, что и даёт полную гарантию O(n log n) при O(1) памяти - здесь показан упрощённый, но корректный и устойчивый вариант той же идеи на уровне отдельных элементов.

Как это работает

Упрощённая версия из этого урока сдвигает элементы по одному, а настоящий WikiSort двигает целые блоки размера примерно √n за один шаг. Каждый прогон делится на такие блоки, и вместо десятков отдельных вставок алгоритм переставляет уже собранные блоки местами, как кубики - это на порядок сокращает число операций перемещения при большом n.

Чтобы переставлять блоки без выделения памяти, WikiSort сначала выбирает внутренний буфер - примерно √n элементов с уникальными значениями, которые временно откладываются в сторону внутри самого массива (никакой отдельной памяти не выделяется). Этот буфер служит рабочей областью для блочных перестановок и локальных слияний внутри одного прогона.

Блоки из левого прогона помечаются меткой A, из правого - B. Алгоритм переставляет их с помощью сортировки выбором по блокам: находит для каждой позиции блок с наименьшим первым элементом и меняет местами целиком. После такой перестановки блоки идут в нужном порядке, но их внутреннее содержимое ещё не слито - для этого запускается локальное слияние с использованием буфера и бинарного поиска точки вставки, что снижает число сравнений на сильно неравных по длине прогонах.

Если в прогоне меньше √n различных значений (например, массив из 1000 повторяющихся 7 и 3), набрать буфер из уникальных элементов не получается. В этом случае WikiSort переключается на более медленный, но всё ещё безбуферный режим слияния - те же повороты подмассива, что и в упрощённой версии этого урока, только применённые к целым блокам. Именно поэтому WikiSort остаётся корректным на любых данных, а не только на входах с достаточным разнообразием значений.

Сложить эти части в оценку O(n log n) можно так: как и в обычном merge sort, длина прогона удваивается на log₂ n уровнях. На каждом уровне суммарная работа по перестановке блоков и локальным слияниям пропорциональна n - блоков O(√n), каждый размером O(√n), и перестановка блока стоит O(√n), что в сумме и даёт O(n) на уровень. Итог - O(n log n) сравнений и перемещений при использовании лишь O(1) дополнительных переменных (буфер живёт внутри самого массива, а не вне него).

Идея слияния в постоянной дополнительной памяти не нова - на неё ещё в 1969 году указал советский математик М. А. Кронрод, а полноценный алгоритм с доказанной сложностью O(n log n) описали Бин-Чао Хуан и Майкл Ланглуа в конце 1980-х в статье о быстром устойчивом слиянии в постоянной памяти. WikiSort (2014) и родственный ему Grailsort - практические, читаемые реализации именно этой более ранней академической идеи.

Инженерный компромисс становится виден в сравнении с Timsort: там, где Timsort тратит до O(n) памяти на буфер, но выигрывает за счёт агрессивного обнаружения уже упорядоченных прогонов и галопирующего слияния (galloping merge) на реальных, часто частично отсортированных данных, WikiSort жертвует этой адаптивностью ради жёсткого потолка памяти. Блочная сортировка выигрывает не скоростью на типичных данных, а гарантией - O(1) память и O(n log n) в худшем случае одновременно, без исключений.

Нюансы выбора

Многократная сортировка больших наборов записей на устройстве с ограниченной оперативной памятью, где даже временный буфер размером в проценты от общего объёма данных недопустим - например, при сортировке логов на встроенном контроллере с килобайтами свободного ОЗУ.

Выбор между WikiSort и Timsort сводится к одному вопросу: что важнее, жёсткая гарантия по памяти или средняя скорость на реальных данных? Python, Java и V8 выбрали Timsort ради адаптивности; блочная сортировка выигрывает только тогда, когда память - это твёрдый лимит, а не просто желательная экономия.

Сортировка записей по нескольким ключам подряд (например, сначала по отделу, потом по имени), где важно не потерять порядок предыдущей сортировки - устойчивость здесь не опция, а требование корректности, и блочная сортировка даёт её без платы памятью.

Когда память не ограничена и данные - случайные, без встроенной структуры, блочная сортировка почти всегда проигрывает по скорости и quicksort, и Timsort: лишняя работа по перестановке блоков и выбору буфера окупается только жёстким лимитом памяти, а не сама по себе.

По трём осям сравнения с соседями по классу: память - строго O(1), лучше и merge sort, и Timsort. Устойчивость - есть, как у merge sort и Timsort, но не у quicksort и heap sort. Скорость на случайных данных - хуже всех перечисленных из-за накладных расходов на блоки и буфер. Блочная сортировка занимает нишу там, где первая ось важнее третьей.

Примеры в коде

WikiSort появился в 2014 году как открытый проект программиста, публиковавшегося под ником BonzaiThePenguin, - название отсылает к тому, что идея алгоритма и его описание собирались коллективно, по образцу википедии, из разрозненных академических источников 1980-х годов.

Grailsort, созданный программистом Андреем Астрелиным (известным под ником Mrrl), - независимая реализация той же идеи блочного слияния, которая легла в основу нескольких портов на C, C#, Java и Rust; ей пользуются в первую очередь в исследовательских и учебных проектах по алгоритмам сортировки, а не в промышленных стандартных библиотеках.

Академический фундамент заложила статья Бин-Чао Хуана и Майкла Ланглуа о слиянии двух отсортированных последовательностей в постоянной дополнительной памяти - именно оттуда взяты идея блочных перестановок и использования части массива как временного буфера, которые WikiSort превратил в работающий, читаемый код тридцать с лишним лет спустя.

Ни один массовый язык программирования не использует блочную сортировку как сортировку по умолчанию: CPython, V8 и OpenJDK выбрали Timsort, потому что на типичных, частично упорядоченных входах адаптивность и галопирующее слияние дают лучшую среднюю скорость, чем строгий потолок памяти WikiSort.

Практическая ниша блочной сортировки - это код, где malloc или new вообще недопустимы во время сортировки: прошивки микроконтроллеров, драйверы и модули ядра, где выделение памяти запрещено правилами безопасности или бюджетом ОЗУ, а устойчивая сортировка записей всё равно нужна.

Когда применять

• Когда одновременно нужны устойчивость, гарантия худшего случая O(n log n) и жёсткое ограничение памяти - сочетание, которое merge sort, quicksort и heap sort по отдельности не дают.
• Во встраиваемых системах, где выделение O(n) буфера для сортировки недопустимо, но стабильность сортировки критична (например, сортировка записей по нескольким ключам).

Примеры из практики

• WikiSort - открытая реализация 2014 года (Mike McFadden), названная в честь совместной разработки идеи на Wikipedia; демонстрирует, что O(1)-памятный устойчивый merge sort практически реализуем.
• Grailsort и другие блочные сортировки** - семейство алгоритмов, вдохновлённых работой Хуанга и Ланглуа (Huang-Langston) по слиянию блоков, используемых в исследовательских и embedded-контекстах.