Сортировка слиянием

Сортировка слиянием (MergeSort)

Описание алгоритма

Допустим, нам надо отсортировать массив из $N$ чисел. Заметим, что если в нем только одно число($N = 1$), то массив уже отсортирован. Иначе предположим, что массивы размеров меньше $N$ мы уже умеем сортировать. Тогда сделаем следующее: разделим массив на две примерно равные части (просто делим пополам), отдельно отсортируем левую, отдельно отсортируем правую часть. Нам останется только объединить эти два массива и получить результат.

Пример:

Пусть дан массив $a = [7, 0, 1, 3, 5, 2, 6, 4]$. В таблице ниже показано, в каком порядке будут происходить деления и как потом ответ будет собираться из отсортированных кусочков.

Разделяем
7 0 1 3 5 2 6 4
7 0 1 3				5 2 6 4
7 0		1 3		5 2		6 4
7	0	1	3	5	2	6	4
Сливаем
0 7		1 3		2 5		4 6
0 1 3 7				2 4 5 6
0 1 2 3 4 5 6 7

Функция Merge

Научимся сливать (объединять) два отсортированных массива. Для этого воспользуемся техникой двух указателей. Пусть указатель $p_1$ стоит на некотором элементе первого массива, указатель $p_2$ на элементе второго массива. Будем поддерживать условие, что сейчас в отсортированный массив надо добавить либо элемент $p_1$, либо $p_2$. Какой именно - можно узнать, сравнив между собой эти два элемента. Если $a[p_1] \le b[p_2]$, то надо сложить в ответ $a[p_1]$ и сдвинуть $p_1$ на единицу вправо. Иначе делаем то же самое, но уже с $p_2$.

Количество смещений двух указателей не превосходит суммы длин двух массивов, поэтому такое слияние выполнится за $O(n + m)$, где $n, m$ - длины двух массивов.

Асимптотика

Вычислим итоговое время работы MergeSort.

Первое доказательство - наглядное

Вспомним наш пример. Заметим, что каждый уровень состоит из одинакового количества элементов, на каждом уровне происходит серия операций merge, но суммарно на каждом уровне все они выполнятся за $O(n)$, так как время на merge линейно зависит от количества чисел в массивах. Теперь оценим количество уровней. На каждом размер сортируемого блока уменьшается в два раза, быть меньше единицы этот блок не может(иногда они вырождаются в пустые блоки, если длины массива - не степень двойки), поэтому уровней будет столько, сколько раз $n$ можно поделить на $2$. Это $\log n$. Тогда весь алгорритм работает за $O(n\log n)$.

Второе доказательство - формальности

Пусть $T(n)$ - время, за которое мы умеем сортировать массив длины $n$. Предположим, что $T(n) < Cn\log n$ для некоторой константы $C$. Теперь посмотрим, из чего складывается время сортировки:

$T(n) = 2T(n/2) + An$, где $A$ - какая-то константа, а $An$ - время на merge.

$T(n) < 2C\frac{n}{2}\log \frac{n}{2} + An =Cn\log \frac{n}{2} + An = n(C\log n - C + A) < Cn\log n$

если $C > A$. Такие константы мы можем подобрать, поэтому доказана верхняя оценка $n\log n$ на время работы сортировки слиянием.

---

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko