Сортировка слияниями проводится по такой схеме. Первым проходом по массиву сортируются пары соседних элементов. Далее проводится слияние уже отсортированных соседних пар, затем - соседних четверок и т. д. Продолжая этот процесс, мы упорядочим весь исходный массив. Трудоемкость подобной сортировки можно оценить в O(n×log₂(n)) операций, но её трудно организовать in situ (на месте). Как правило, приходится использовать дополнительную память.

адача 4. Составить рекурсивную программу-функцию сортировки слияниями массива, заданного вектором v = (v₀   v₁  ...  v_n-1).

Решение. Нетрудно себе представить ранее описанную процедуру в рекурсивном виде. При этом базой рекурсии удобно считать вектор длины 1, а декомпозицию задачи организовать разбиением исходного вектора на два приблизительно равных по длине массива. Соответствующая программа сортировки может быть задана функцией sortmer(v).