Суть: разбиваем массив пополам, с полученными массивами делаем то же самое и так далее до массива с одним элементов. Затем объединяем эти массивы. Этот алгоритм основан на такой парадигме как Divide and Conquer
[https://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg](https://lh7-us.googleusercontent.com/uB_VKdwUbwAcXU32v85BhuzX_2aOo619utiGh0bhdoDCs_QHBngBBa1oy7JqApvML0rSXNWMK5SL5X02E1ZkXtHfraAMIgLXTIuv5Ghk37kMWh2OoZPRihx0jOa7AR07Pet60lASegsDxCIZVrh9Iw)
https://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg
Очень удобно решать через рекурсию!
1 шаг – разбиваем массив на две равные части
2 шаг – продолжаем бить части до того, как останется по одному элементу
3 шаг – делаем процедуру слияния (merge), объединяя массивы в один: ставим индексы на начало обоих массивов (они уже отсортированы), берём минимальный элемент из тех двух, на которые указывают указатели, сдвигаем указатель массива, из которого взяли элемент и делаем то же самое до тех пор, пока указатель не дойдёт до конца одного из массивов. Потом надо, чтобы он “добежал” второй массив.
Сложность по времени: O(n * log(n)),
где log2(n) - затраты на разбиение на части (красный цвет на рисунке), n - постепенная сортировка этих частей (зеленый цвет на рисунке). Минус сортировки слиянием заключается в привлечении дополнительной памяти!
