Сортировка слиянием
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
- Сортируемый массив разбивается на две части примерно одинакового размера;
- Каждая из получившихся частей сортируется отдельно, например - тем же самым алгоритмом;
- Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.
Алгоритм
Алгоритм был изобретён Джоном фон Нейманом в 1945 году.
Время работы алгоритма порядка O(n * log n) при отсутствии деградации на неудачных случаях, которая есть больное место быстрой сортировки (тоже алгоритм порядка O(n * log n), но только для лучшего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти - возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.
Популярная реализация требует однократно выделяемого временного буфера памяти, равного сортируемому массиву, и не имеет рекурсий.
Шаги реализации:
- InputArray = сортируемый массив, OutputArray = временный буфер
- над каждым отрезком входного массива InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE) выполняется какой-то вспомогательный алгоритм сортировки, например, сортировка Шелла или qsort
- устанавливается ChunkSize = MIN_CHUNK_SIZE
- сливаются два отрезка InputArray[N * ChunkSize..(N + 1) * ChunkSize) и InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize) попеременным шаганием слева и справа, результат помещается в OutputArray[N * ChunkSize..(N + 2) * ChunkSize], и так для всех N, пока не будет достигнут конец массива.
- ChunkSize удваивается
- если ChunkSize стал >= размера массива - то конец, результат в OutputArray, который (ввиду перестановок, описанных ниже) есть либо сортируемый массив, либо временный буфер, во втором случае он целиком копируется в сортируемый массив.
- иначе меняются местами InputArray и OutputArray перестановкой указателей, и все повторяется с пункта 4.
Псевдокод сортировки слиянием на С++
02 | function merge(left,right) |
04 | while length(left) > 0 and length(right) > 0 |
05 | if first(left) ≤ first(right) |
06 | append first(left) to result |
09 | append first(right) to result |
15 | append right to result |
Вывод по сортировке слиянием
Такая реализация также поддерживает размещение сортируемого массива и временного буфера в дисковых файлах, т.е. пригодна для сортировки огромных объемов данных. Реализация ORDER BY в СУБД MySQL при отсутствии подходящего индекса устроена именно так (источник: filesort.cc в исходном коде MySQL).