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

Проще всего отсортировать файл так: загрузить его, отсортировать его в памяти, затем записать результат. Если файл настолько велик, что загрузить его в оперативную память не удается, приходится применять разнообразные методы внешней сортировки. Мы рассмотрим здесь внешнюю сортировку, использующую выбор с замещением для получения начальных отрезков, за которым следует многофазное слияние для слияния отрезков в один отсортированный файл. Очень рекомендую книжку Кнута [1998] - неисчерпаемый источник дополнительной информации.
 

Теория

Для определенности я буду считать, что данные располагаются на одной или более бобин магнитной ленты. На рис. 4-1 иллюстрируется трехпутевое многофазное слияние. В начале, на фазе А, все денные находятся на лентах Т1 и Т2. Предполагается, что начало каждой ленты - внизу картинки. Имеется два упорядоченных отрезка на Т1: 4-8 и 6-7. На ленте Т2 - один отрезок 5-9. На фазе B мы сливаем первый отрезок с ленты Т1 (4-8) с первым отрезком Т2 (5-9) и получаем более длинный отрезок на ленте Т3 (4-5-8-9). На фазе С мы просто переименовываем ленты, так чтобы можно было повторить слияние. На фазе D мы повторяет слияние, получив результат на ленте Т3.
Фаза T1 T2 T3
A 7
6
8
4		 9
5
B 7
6
9
8
5
4
C 9
8
5
4		 7
6
D

9
8
7
6
5
4

Рис. 4-1: Сортировка слиянием
В приведенном тексте опущены некоторые интересные детали. Например, как были созданы начальные возрастающие отрезки? Кроме того, вы обратили внимание: они слиты так, что не потребовалось создавать дополнительные отрезки? Перед тем, как я объясню, каким образом были созданы начальные отрезки, позвольте мне слегка отвлечься.

В 1202 Леонардо Фибоначчи в книге Liber Abbaci (Книга об абаке) рассмотрел следующую задачу: Сколько пар кроликов можно получить за год, если в начале была лишь одна пара? Предположим, что каждая пара кроликов производит потомство каждый месяц, становится способной к воспроизводству также за один месяц, а также, что кролики не мрут. Спустя один месяц у нас будет 2 пары кроликов, спустя 2 месяца - 3 пары. Спустя еще месяц исходная пара и пара, рожденная в 1-й месяц, дадут каждая по паре, так что всего у нас будет 5 пар. Ряд, в котором каждый член является суммой двух предыдущих членов, называется последовательностью Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... .
Любопытно, что ряды Фибоначчи встречаются в самых разных ситуациях - от изучения расположения цветов на растении до оценки эффективности алгоритма Евклида. Неудивительно, что издается журнал Fibonacci Quarterly (Ежеквартальный Фибоначчи). И, как вы уже, конечно, догадались, ряд Фибоначчи имеет прямое отношение к порождению начальных отрезков при внешней сортировке.
 
Вспомним, что сначала у нас был один отрезок на ленте Т2 и два - на ленте Т1. Обратите внимание - числа {1,2} являются двумя последовательными членами ряда Фибоначчи. После первого слияния у нас появился один отрезок на Т1 и один на Т2. Заметим, что числа  {1,1} - тоже два последовательных члена ряда Фибоначчи, только на шаг раньше. Мы, таким образом, готовы предсказать, что если бы у нас было 13 отрезков на Т2 и 21 на Т1 {13,21}, то после одного прохода у нас было бы 8 отрезков на Т1 и 13 на Т3 {8,13}. Последовательные проходы привели бы нас к отрезкам {5,8}, {3,5}, {2,3}, {1,1} и {0,1}, т.е. всего понадобилось бы 7 проходов. Этот порядок идеален, при нем требуется минимальное число проходов. Если данные действительно находятся на ленте, минимизация числа проходов очень важна, поскольку ленты может понадобиться снимать и устанавливать после каждого прохода. В случае, когда имеется более двух лент, применяются числа Фибоначчи высшего порядка.

Сначала все данные располагаются на одной ленте. Лента читается и отрезки распределяются по другим лентам, имеющимся в системе. после того, как созданы начальные отрезки, они сливаются, как описано выше. Один из методов, который можно использовать для создания начальных отрезков, состоит в чтении порции записей в память, их сортировке и записи результата на ленту. Выбор с замещением позволяет нам получать более длинные отрезки. Этот алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут исчерпаны входные данные:

На рис. 4-2 выбор с замещением иллюстрируются для совсем маленького файла. Начало файла - справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла - с ключом 4. Процесс продолжается до шага F,  где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего.
Шаг Вход Буфер Выход
A 5-3-4-8-6-7
B 5-3-4-8 6-7
C 5-3-4 8-7 6
D 5-3 8-4 7-6
E 5 3-4 8-7-6
F 5-4 3 | 8-7-6
G 5 4-3 | 8-7-6
H 5-4-3 | 8-7-6

Рис. 4-2: Выбор с замещением
Обратите внимание мы храним записи в буфере до тех пор, пока не наступит время записать их в выходной файл. Если вход случаен, средняя длина отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть как-то упорядочены, отрезки могут быть очень длинными. Вот почему этот метод, вообще говоря, более эффективен промежуточных, частичных сортировок.

Прочитав из входного файла очередную запись, мы ищем наименьший ключ, который >= последнего считанного. При этом мы, конечно, можем просто сканировать записи в буфере. Однако, если таких записей тысячи, время поиска может оказаться недопустимо большим. Если на этом этапе использовать двоичные деревья, нам понадобится всего лишь lg n сравнений.

Реализация

В кодах внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки. Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков.