Вопрос 52.1. Как можно повысить эффективность внешней сортировки слиянием

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

Главная идея, которая лежит в основе сортировки слиянием, заключается в том, что мы организуем файл в виде постепенно увеличивающихся серий, т.е. последовательностей записей r₁...,r_k, где ключ r_i не больше, чем ключ r_i+1, 1 < i < k. [3] Мы го­ворим, что файл, состоящий из 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, однако и его записи тоже отсортированы.

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

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

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

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

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

В этом случае можно использовать достаточно простой процесс чтения по одной серии из файлов 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 п) проходов по данным, хранящимся в единственном файле. Этот показатель яв­ляется существенным улучшением в сравнении с О(п) проходами, которые требуются многим из алгоритмов сортировки.