Сортировка слиянием
Алгоритм был изобретён
Джоном фон Нейманом в 1945 году.
Идея сортировки
1) Возьмем массив. Если он состоит из одного элемента, то он уже отсортирован
2) Если элементов больше, чем один, то разобьем массив на две равные части (с точностью до единицы) и отсортируем каждую часть, применив рекурсивно тот же алгоритм.
3) Далее, "сольем" все отсортированные части в один массив.
Как "слить" все части в один массив?
- Будем хранить индексы начала двух отсортированных частей.
- Создадим новый список следующим образом:
- из двух элементов, на которые указывают индексы, будем выбирать меньший и дописывать его в новый список;
- сдвинем индекс, элемент которого мы взяли, на следующий элемент списка;
- если закончились элементы в одной из сливаемых частей, то элементы второй мы просто добавим в конец итогового списка.
- Полученный отсортированный список необходимо поместить на место сливаемых частей.
Псевдокод алгоритма слияния
Функция сливает две части массива
a -
[left;mid) и
[mid;right)
ФУНКЦИЯ merge(a, left, mid, right) // a - массив, размерностью n; left, mid, right - целые числа, индексы элементов массива
it1 = 0
it2 = 0
result: int[right - left] // результирующий массив
ПОКА left + it1 < mid И mid + it2 < right
ЕСЛИ a[left + it1] < a[mid + it2]
result[it1 + it2] = a[left + it1]
it1 += 1
ИНАЧЕ
result[it1 + it2] = a[mid + it2]
it2 += 1
ПОКА left + it1 < mid
result[it1 + it2] = a[left + it1]
it1 += 1
ПОКА mid + it2 < right
result[it1 + it2] = a[mid + it2]
it2 += 1
ДЛЯ i ОТ 0 ДО it1 + it2
a[left + i] = result[i]
ВЕРНУТЬ a
Рекурсивный алгоритм сортировки слиянием
Функция сортирует подотрезок массива
a с индексами в полуинтервале
[left; right)
ФУНКЦИЯ mergeSortRecursive(a, left, right) // a - массив, left, right - индексы полуинтервала сортировки
if left + 1 >= right
ВЕРНУТЬ a
mid = (left + right) / 2
mergeSortRecursive(a, left, mid)
mergeSortRecursive(a, mid, right)
merge(a, left, mid, right)
ВЕРНУТЬ a
Итеративный алгоритм сортировки слиянием
При итеративном алгоритме используется на
O(logn) меньше памяти, которая раньше тратилась на рекурсивные вызовы.
ФУНКЦИЯ mergeSortIterative(a, n) // a - массив; n - длина массива
ДЛЯ i ОТ 1 ДО n, ШАГ i *= 2
ДЛЯ j ОТ 0 ДО n - i, ШАГ j += 2 * i
merge(a, j, j + i, min(j + 2 * i, n))
ВЕРНУТЬ a
Время работы
Для оценки времени работы, составим рекуррентное соотношение.
Пусть
T(n) - время сортировки массива длины
n, тогда для сортировки слиянием справедливо:
T(n) = 2T(n/2)+O(n)
O(n) - время, необходимое на то, чтобы слить два массива длины
n.
Распишем это соотношение:
T(n) = 2T(n/2) + О(n) = 4T(n/4) + 2O(n) = ... = T(1) + log(n)O(n) = O(nlog(n)).
Сложность алгоритма O(nlog(n))
Дополнительные материалы
1)
Сортировка слиянием. Вики-конспекты ИТМО.