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

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

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

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

Пример:

Пусть дан массив $a = [7, 0, 1, 3, 5, 2, 6, 4]$.

0	1	2	3	4	5	6	7
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

Функция Merge

Научимся сливать (объединять) два отсортированных массива.

Асимптотика

---

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

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