Мой перевод статьи Гвидо ван Россума:
Меня тут в шутку спросили: смогу ли я отсортировать миллион 32-битных int'ов в 2 мегабайтах памяти на Питоне. Во время размышления, мне пришло в голову задействовать механизм ввода-вывода с использованием буферной памяти.
Вообще, это именно шуточный вопрос — одни только данные займут 4 мегабайта, при условии бинарного представления! Правда, можно пойти на хитрость — взять файл, содержащий миллион 32-битных int'ов. Как же отсортировать их, используя минимальное количество памяти? Это должна быть какая-то разновидность сортировки слиянием, в которой небольшие куски данных сортируются и записываются во временный файл, после чего происходит слияние временных файлов для получения окончательного результата.
Вот мое решение:
Меня тут в шутку спросили: смогу ли я отсортировать миллион 32-битных int'ов в 2 мегабайтах памяти на Питоне. Во время размышления, мне пришло в голову задействовать механизм ввода-вывода с использованием буферной памяти.
Вообще, это именно шуточный вопрос — одни только данные займут 4 мегабайта, при условии бинарного представления! Правда, можно пойти на хитрость — взять файл, содержащий миллион 32-битных int'ов. Как же отсортировать их, используя минимальное количество памяти? Это должна быть какая-то разновидность сортировки слиянием, в которой небольшие куски данных сортируются и записываются во временный файл, после чего происходит слияние временных файлов для получения окончательного результата.
Вот мое решение: