- Сортировка слиянием
-
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
- Сортируемый массив разбивается на две части примерно одинакового размера;
- Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
- Два упорядоченных массива половинного размера соединяются в один.
1.1. - 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
3.1. Cоединение двух упорядоченных массивов в один.
Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда:
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.
3.3. "Прицепление" остатка.
Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.Псевдокод алгоритма слияния без "прицепления" остатка на C++-подобном языке:
L = *In1; R = *In2; if( L == R ) { *Out++ = L; In1++; *Out++ = R; In2++; } else if( L < R ) { *Out++ = L; In1++; } else { *Out++ = R; In2++; }
Алгоритм был изобретён Джоном фон Нейманом в 1945 году.[1]
В приведённом алгоритме на C++-подобном языке используется проверка на равенство двух сравниваемых элементов подмассивов с отдельным блоком обработки в случае равенства. Отдельная проверка на равенство удваивает число сравнений, что замедляет алгоритм и усложняет код программы. Вместо отдельной проверки на равенство и отдельного блока обработки в случае равенства можно использовать одну общую проверку if( L <= R ) и общий блок обработки во всех случаях, что вдвое уменьшает число проверок, повышает быстродействие программ, почти вдвое уменьшает код программы и упрощает алгоритм.
Псевдокод улучшенного алгоритма слияния без "прицепления" остатка на C++-подобном языке:
L = *In1; R = *In2; if( L <= R ) { *Out++ = L; In1++; } else { *Out++ = R; In2++; }
Две операции пересылки в переменные L и R упрощают некоторые записи в программе, что может оказаться полезным в учебных целях, но в действительных программах они потребляют дополнительное машинное время и дополнительные ячейки памяти, поэтому в действительных программах они не нужны и их можно удалить, что ещё более увеличит быстродействие, уменьшит расход памяти и сократит программный код.
Псевдокод ещё более улучшенного алгоритма слияния без "прицепления" остатка на C++-подобном языке:if( *In1 <= *In2 ) { *Out++ = *In1; In1++; } else { *Out++ = *In2; In2++; }
Время работы алгоритма порядка O(n * log n) при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка O(n * log n), но только для среднего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти — возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.
Популярная реализация требует однократно выделяемого временного буфера памяти, равного сортируемому массиву, и не имеет рекурсий. Шаги реализации:
- InputArray = сортируемый массив, OutputArray = временный буфер
- над каждым отрезком входного массива InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] выполняется какой-то вспомогательный алгоритм сортировки, например, сортировка Шелла или быстрая сортировка.
- устанавливается 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.
Такая реализация также поддерживает размещение сортируемого массива и временного буфера в дисковых файлах, то есть пригодна для сортировки огромных объемов данных. Реализация ORDER BY в СУБД MySQL при отсутствии подходящего индекса устроена именно так (источник: filesort.cc в исходном коде MySQL).
Пример реализации алгоритма простого двухпутевого слияния на псевдокоде:
function mergesort(m) var list left, right, result if length(m) ≤ 1 return m else middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = mergesort(left) right = mergesort(right) result = merge(left, right) return result end if
Есть несколько вариантов функции merge(), наиболее простой вариант может выглядеть так:
function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) end if if length(left) > 0 append left to result if length(right) > 0 append right to result return result
Примечания
- ↑ Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. — 2nd. — Addison-Wesley, 1998. — P. 159. — ISBN 0-201-89685-0
Литература
- Ананий В. Левитин Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 169-172. — ISBN 5-8459-0987-2
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
Ссылки
- Многофазное слияние на algolist.manual.ru
- Сортировка слиянием — восходящая сортировка, естественная сортировка, измерение быстродействия.
Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.