вторник, октября 30, 2012

Статья про сортировку 1 миллиона чисел с ограничением по памяти

На Stack Overflow кто-то сформулировал следующую задачу: по сети приходят восьмизначные числа. Их приходит миллион штук, их надо отсортировать и переслать дальше. Проблема в том, что устройство, на которое они приходят - это компьютер с 1 Мб оперативной памяти. И это вся память что есть, жесткого диска нет. Короче говоря, реализовать сортировку по-тупому не получится, ибо не лезет.

Вот здесь описано решение этой задачи 1MB Sorting Explained. Подход выбран следующий: числа накапливать и сортировать кусками. Отсортированную последовательность хранить в пожатом виде.