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

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

Сортировка, при которой всегда сливаются две самые длинные из возможных последовательностей, является естественным слиянием. В данной сортировке объединяются серии максимальной длины.

Алгоритм сортировки естественным слиянием

Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2. Распределение происходит следующим образом: поочередно считываются записи a_i исходной последовательности (неупорядоченной) таким образом, что если значения ключей соседних записей удовлетворяют условию f(a_i)<=f(a_i+1), то они записываются в первый вспомогательный файл f1. Как только встречаются f(a_i)>f(a_i+1), то записи a_i+1 копируются во второй вспомогательный файл f2. Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом серии образуют упорядоченные последовательности.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2.

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

Символ "`" обозначает признак конца серии.

Признаками конца сортировки естественным слиянием являются следующие условия:

• количество серий равно 1 (определяется на фазе слияния).
• при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.

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

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

Ключевые термины

Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память.

Двухпутевое слияние – это сортировка, в которой данные распределяются на два вспомогательных файла.

Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние.

Длина серии – это количество элементов в серии.

Естественное слияние – это сортировка, при которой всегда сливаются две самые длинные из возможных серий.

Многопутевое слияние – это сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.

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

Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.

Простое слияние – это одна из сортировок на основе слияния, в которой длина серий фиксируется на каждом шаге.

Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.

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

Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.

Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов доступных в данный момент.

Фаза – это действия по однократной обработке всей последовательности элементов.

Краткие итоги

1. Внешние сортировки применяются к данным, которые хранятся во внешней памяти. Внешние сортировки применяются, если объем сортируемых данных превосходит допустимое место в ОЗУ.

2. Внешние сортировки, по сравнению с внутренними, характеризуются проигрышем по времени за счет обращения к внешним носителям.

3. К наиболее известным алгоритмам внешних сортировок относятся: сортировки слиянием (простое слияние и естественное слияние); улучшенные сортировки (многофазная сортировка и каскадная сортировка).

4. Алгоритмы внешних сортировок отличаются по реализации числом фаз и путей.

5. Простое слияние является одной из сортировок на основе слияния, в которой длина серий фиксируется на каждом шаге.

6. Естественное слияние является сортировкой, при которой всегда сливаются две самые длинные из возможных серий.

7. Число чтений или перезаписей файлов при использовании метода естественного слияния будет не хуже, чем при применении метода простого слияния, а в среднем – даже лучше. Однако в данном методе увеличивается число сравнений за счет распознавания концов серий.