Изменения
Нет описания правки
Научившись сливать с использованием O(1) дополнительной памяти оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем. == Слияние ===== Шаг 1 ===Разобьем наш массив на группы === Шаг 2 === =Ссылкии литература=
*[http://e-maxx.ru/bookz/files/knuth_3.djvu| Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4]
*[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA]
