Сортировка слиянием также следует стратегии «разделяй и властвуй». Разделяем исходный массив на два равных подмассива. Повторяем сортировку слиянием для этих двух подмассивов и объединяем обратно.
Цикл деления повторяется, пока не останется по одному элементу в массиве. Затем объединяем, пока не образуем полный список.
Алгоритм сортировки состоит из четырех этапов:
Найти середину массива.
Сортировать массив от начала до середины.
Сортировать массив от середины до конца.
Объединить массив.
Для объединения напишем отдельную функцию merge().
Алгоритм объединения массивов:
Циклично проходим по двум массивам..
В объединяемый ставим тот элемент, что меньше.
Двигаемся дальше, пока не дойдем до конца обоих массивов.
