В основе данного метода внутренней сортировки лежит процедура слияния двух упорядоченных таблиц. Эти таблицы должны быть объединены таким образом, чтобы получилась одна упорядоченная таблица.
Пусть имеются две таблицы А и В, упорядоченные по возрастанию ключей . Слияние заключается в поочередной пересылке элементов из таблиц А и В в зону формирования С. Порядок пересылки в зону формирования зависит от результата попарного сравнения ключей таблиц А и В.
Сортировка слиянием производится на основе использования рассмотренной выше процедуры. Сущность сортировки состоит в том, что упорядочиваемая таблица разделяется на равные группы элементов. Группы упорядочиваются, а затем попарно сливаются, образуя новые группы, содержащие вдвое больше элементов.
Процедура слияния двух групп должна иметь такие параметры:

Рис. 1.  

На первом этапе каждая группа содержит два соседних элемента исходного массива. Элементы внутри групп упорядочиваются (напр., методом вставки). Затем происходит попарное слияние групп. Количество групп в списке уменьшается вдвое до тех пор, пока не будет получена одна упорядоченная группа. Если число элементов нечетное, то вводится дополнительный элемент с максимальным значением. После сортировки он отбрасывается. Если число групп, сформированных на первом этапе, нечетно, то непарная группа переписывается без слияния. Рассмотренный метод двухпутевой сортировки слиянием весьма эффективен. Поскольку при сортировке нужно выполнить log2(n) проходов,то необходимое суммарное число сравнений равно,примерно,n*log2(n). Одним из недостатков данного метода является требование большого резерва памяти:

S = [n/2].