Всех с Новым годом!
Быстрое решение также возможно. Если мы можем паковать сортированные числа так, чтобы они занимали меньше памяти, то этим мы и воспользуемся: прочитаем столько чисел, сколько поместится в текущую свободную память, быстро их отсортируем, сожмем, используя подходящий prefix-free код, сольем с предыдущей отсортированной последовательностью и получим новую текущую отсортированную последовательность. Повторить до получения результата (4-5 итераций для миллиона чисел).
Вместо 45 минут сортировки вставкой получаем всего ~0.5 секунд (qsort() без ограничений памяти работает ~0.33 секунд). Отмечу, что опять миллион оказывается хорошо подобранным параметром задачи - он достаточно далеко отстоит от теоретического предела представимости в 2 МБ сортированной последовательности, чтобы позволить быструю сортировку (т.е. малое количество итераций).
Мое решение полностью (идеи, код, доказательство, программы) в
olg2002.livejournal.com.
