Внешняя сортировка

Одна БольшаЯ КомпаниЯ (сокращенно: БЯКЯ) очень любит давать соискателям задачу про внешнюю сортировку. И я там был, мёд пиво пил, по усам текло, да в рот не попало. В БЯКЯ меня не взяли. Но официальные причины отказа никак не касались самого алгоритма, за оптимальность которого я, собственно, больше всего и боролся. Поэтому я, не имея конечной оценки качества алогритма, хочу его опубликовать и получить "по рогам" уже по существу. Ну собственно ценные замечания по стилистике тоже с радостью послушаю. Единственное, что после слов "так верстают только мудаки" очень прошу не забывать писать как же надо верстать на самом деле :)))

Итак, что такое эта самая внешняя сортировка? Это когда нам надо отсортировать такое количество данных, которое не влезает в оперативную память. Данные, очевидно, хранятся на диске - надо их пересортировать и обратно на диск положить.

Ну, к примеру, есть файл на 100 гигабайт. Файл рассматриваем как совокупность беззнаковых целых 32-битных чисел. Т.е. каждый 4 байта файла - число. Есть машина на которой невозможно выделить боле 256 мегабайт памяти. Сортируйте.

Общий принцип решения становится ясен после прочтения одноименной вики-статьи. Расскажу, как я её понял.

Итак, у нас естественным образом выделяются две фазы.

1. Фаза последовательной сортировки: "рубим" весь файл на чанки, так чтобы каждый чанк целиком влезал в оперативную память, загружаем последовательно каждый чанк в память, сортируем стандартными методами внутренней сортировки(std::sort), кладём отсортированный чанк на диск, берём следующий чанк и т.д.

2. Фаза слияния. У нас есть много чанков, каждый из которых отсортирован, надо их "слить" в результирующий, глобально-отсортированный файл.

Для второй фазы я выбрал путь однопроходного слияния, хотя есть и другие варианты (и хотелось бы их впоследствии обсудить с общественностью). Принцип очень простой: представьте себе колоду карт. Теперь мы раскладываем эту колоду в несколько стопок рубашками вниз. Про каждую стопку известно, что любая вышележащая карта в стопке младше нижележащей из той же стопки. Таким образом посмотрев на все верхние карты всех стопок мы берём саму младшую из них - и, очевидно, это будет самая младшая карта в колоде. Снимаем её и кладём в новую стопку, под названием "результат". Повторяем предыдущее действие - т.е. снова смотрим все стопки (кроме "результата") и выбираем наименьшую из верхних карт и т.д. В конце концов в стопке "результат" мы получим полностью отсортированную колоду.

Теперь к нашей задаче. Стопки - это наши предсортированные чанки. Если у нас всего N чисел в исходном файле и M чанков, то наш алгортим должен сделать N операций по выборе минимума из M чисел. Т.е. сложность алгоритма при "лобовой" реализации O(N*M). Сразу хочется ускорить этот момент, благо ничего сложного в этом нет. Предлагаю хранить M "верхних" карт в приоиртетной очереди (std::priority_queue). И на каждом ходу - достаём самую маленькую (константное время) и запихиваем новую открывшуюся (O(ln(M))). В итоге получаем сложность O(N*ln(M)).

Вот впринципе и всё. Но. БЯКЯ, в постановке задачи, особо отметил необходимость эффективной работы в случае многоядерного процессора. Т.е. нужна многопоточность. Такая чтобы работало быстрее, чем без неё.

На сегодня всё, устал писать. Обещаю в течение нескольких дней запостить продолжение про распараллеливание. И выложить на поругание сорцы. Спасибо.