Сортировка слиянием
Содержание
Сортировка слиянием (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