Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Пример сортировки слиянием. Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.
Для решения задачи сортировки эти три этапа выглядят так:
Сортируемый массив разбивается на две части примерно одинакового размера;
Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
Два упорядоченных массива половинного размера соединяются в один.
1.1. - 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
3.1. Cоединение двух упорядоченных массивов в один.
Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда:
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.
3.3. "Прицепление" остатка.
Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.
MergeSort (list, first, last )
list сортируемый список элементов
first номер первого элемента в сортируемой части списка
last номер последнего элемента в сортируемой части списка
if first < last then
middle = (first + last ) / 2
MergeSort (list, first, last )
MergeSort (list, first, last )
MergeSort (list, first, last )
MergeLists (list, first, middle, middle + 1, last)
end if
MergeLists (list, start1, end1, start2, end2)
list упорядочиваемый список элементов
start1 начало списка «А»
end1 конец списка «А»
start2 начало списка «В»
end2 конец списка «В»
// предполагается, что элементы списков А и В следуют в списке list друг за другом
finalStart = start1
finalEnd = end2
indexC = 1
while (start1 <= end1 ) and (start2 <= end2) do
if list [start1] <= list [ start2 [ then
result [ indexC] = list [ start1 ]
start1 = start1 + 1
else
result [ indexC] = list [ start2 ]
start2 = start2 + 1
end if
indexC = indexC + 1
end while
// перенос оставшейся части списка
if ( start1 <= end1) then
for i = start1 to end1 do
result [ indexC] = list [ i ]
indexC = indexC + 1
end for
else
for i = start2 to end2 do
result [ indexC] = list [ i ]
indexC = indexC + 1
end for
end if
//возвращение результатов в список
indexC = 1
for i = finalStart to finalEnd do
list [ i ] = result [ indexC]
indexC = indexC + 1
end for