Вопрос 45.1. В чем состоит алгоритм внешней сортировки слиянием

Сортировка данных с ленты или диска называется внешней сортировкой. Внешняя сортировка сортирует файлы, которые не помещаются целиком в оперативную память. Если сортируемый файл целиком помещается в память (или целиком помещается в массив, то для него мы используем внутренние методы сортировки.

Внешняя сортировка сильно отличается от внутренней. Доступ к файлу является последовательным, а не параллельным как это было в массиве. И поэтому считывать файл можно только блоками и этот блок отсортировать в памяти и снова записать в файл.

Принципиальную возможность эффективно отсортировать файл, работая с его частями и не выходя за пределы части, обеспечивает алгоритм слияния.

Время внешней сортировки зависит от:

• внутренней сортировки частей файла;

• многократного считывания и записи данных на диск;

• ходов головки между актами считывания/записи;

• действий в памяти при слиянии упорядоченных частей

Сортировка слиянием

Главная идея, которая лежит в основе сортировки слиянием, заключается в том, что мы организуем файл в виде постепенно увеличивающихся серий, т.е. последовательностей записей r₁ ... ,r_k , где ключ r_i не больше, чем ключ r_i+1, 1 < i < k.² Мы го­ворим, что файл, состоящий из r₁ ... ,r_k записей, делится на серии длиной k, если для всех r > 0, таких, что ki < т и r_k(i-1)+1, r_k(i-1)+2 , ... , r_ki является последовательно­стью длиной k. Если т не делится нацело на k, т.е. т = pk + q, где q < k, тогда по­следовательность записей r_m-q+1, r_m-q+2 , ... , r_m, называемая хвостом, представляет собой серию длиной q. Например, последовательность целых чисел, показанная на рис. 1, организована сериями длиной 3. Обратите внимание, что хвост имеет дли­ну, меньшую 3, однако и его записи тоже отсортированы.

7 15 29

8 11 13

16 22 31

5 12

Рис. 1. Файл с сериями длиной 3

Главное в сортировке файлов слиянием — начать с двух файлов, например f₁ и f₂, организованных в виде серий длиной k. Допустим, что:

1. количества серий (включая хвосты) в f_i и f₂ отличаются не больше, чем на единицу;

2. по крайней мере один из файлов f_i или f₂, имеет хвост;

3. файл с хвостом имеет не меньше се­рий, чем другой файл.

В этом случае можно использовать достаточно простой процесс чтения по одной серии из файлов f₁ и f₂, слияние этих серий и присоединения результирующей серии длиной 2k к одному из двух файлов g₁ и g₂, организованных в виде серий длиной 2k. Переключаясь между g₁ и g₂, можно добиться того, что эти файлы будут не только организованы в виде серий длиной 2k, но будут также удовлетворять перечисленным выше условиям (1) - (3). Чтобы выяснить, выполняются ли условия (2) и (3), доста­точно убедиться в том, что хвост серий f_l и f₂ слился с последней из созданных серий (или, возможно, уже был ею).

Итак, начинаем с разделения всех п записей на два файла f₁ и f₂, (желательно, чтобы записей в этих файлах было поровну). Можно считать, что любой файл со­стоит из серий длины 1. Затем мы можем объединить серии длины 1 и распреде­лить их по файлам g₁ и g₂ , организованным в виде серий длины 2. Мы делаем f₁ и f₂ пустыми и объединяем g₁ и g₂ в f₁ и f₂, которые затем можно организовать в ви­де серий длины 4. Затем мы объединяем f₁ и f₂,, создавая g₁ и g₂, организованные в виде серий длиной 8, и т.д.

После выполнения i подобного рода проходов у нас получатся два файла, состоящие из серий длины 2ⁱ. Если 2ⁱ > п, тогда один из этих двух файлов будет пустым, а другой будет содержать единственную серию длиной п, т.е. будет отсортирован. Так как 2ⁱ > п при i > logn, то нетрудно заметить, что в этом случае будет достаточно [log n] + 1 прохо­дов. Каждый проход требует чтения и записи двух файлов, длина каждого из них рав­на примерно n/2. Общее число блоков, прочитанных или записанных во время одного из проходов, составляет, таким образом, около 2п/b, где b — количество записей, уме­щающихся в одном блоке. Следовательно, количество операций чтения и записи блоков для всего процесса сортировки равняется О((n log n)/b), или, говоря по-другому, коли­чество операций чтения и записи примерно такое же, какое требуется при выполнении O(log п) проходов по данным, хранящимся в единственном файле. Этот показатель яв­ляется существенным улучшением в сравнении с О(п) проходами, которые требуются многим из алгоритмов сортировки.

В листинге показан код программы сортировки слиянием на языке Pascal. Мы считываем два файла, организованных в виде серий длины k, и записываем два файла, организованных в виде серий длины 2k. Предлагаем читателям, воспользо­вавшись изложенными выше идеями, самостоятельно разработать алгоритм сорти­ровки файла, состоящего из п записей. В этом алгоритме должна logn раз использо­ваться процедура merge (слияние), представленная в листинге 1.