Cортировка слиянием с использованием O(1) дополнительной памяти
Версия от 05:55, 7 июня 2011; 192.168.0.2 (обсуждение)
Научившись сливать с использованием O(1) дополнительной памяти оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером (за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем.
Содержание
Слияние
Шаг 1
Разобьем наш массив на группы
