Изменения

После того, как мы научились сливать с использованием <tex> O(1) </tex> дополнительной памяти и <tex> O(n) </tex> операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пары, то просто ничего не делаем. Выполняем это для всех i от <tex> 2 </tex> до <tex> \lceil ln(n) \rceil </tex>

[[Файл:Freememmerge.png|right|380px|thumb|Пример работы алгоритма слияния]]

На вход алгоритм получает массив, который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Алгоритм состоит из нескольких шагов.