31. Внешняя сортировка. Основные характеристики сортировок методом слияний

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

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

Отрезок, состоящий из одного элемента, упорядочен всегда. Если длина серии фиксирована, то слияние называется простым. Сортировка, при которой всегда сливаются две самые длинные из возможных серий, называется естественным слиянием. Вначале серии распределяются на два или несколько вспомогательных файлов. Распределение серий идет поочередно, т.е. первая серия записывается в первый вспомогательный файл, вторая – во второй и т.д. После того, как произошла запись в последний файл, опять начинается запись серии в первый вспомогательный файл. После распределения всех серий они объединяются в более длинные упорядоченные отрезки: из каждого вспомогательного файла берется по одной серии и они сливаются. Если в каком-то файле серия заканчивается, то следующая пока не рассматривается. Сформированный более длинный упорядоченный отрезок записывается либо в исходный файл, либо в какой-то из вспомогательных файлов, это зависит от вида сортировки. Когда все серии из всех вспомогательных файлов объединены в новые серии, опять начинается их распределение. Так продолжается до тех пор, пока все данные не будут упорядочены.

1. Количество вспомогательных файлов, на которые идет распределение серий.

   • Если данные распределяются на два вспомогательных файла, то сортировка называется двухпутевым слиянием,

   • если на N (N>2) вспомогательных файлов, то – многопутевым слиянием.

2. Количество фаз в реализации сортировки.

   • Фазой называются действия по однократной обработке всего множества.

   • Наименьший процесс, повторение которого составляет процесс сортировки проход (этапом).

   • В двухфазной сортировке отдельно реализуются две фазы:

     1. распределение

     2. и слияние.

   • После того, как произошло распределение данных по вспомогательным файлам, они объединяются и записываются в исходный файл.

   • В однофазной сортировке обе эти фазы объединены в одну.

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

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

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