6. Внешняя сортировка (сортировка последовательностей)
 
   6.1. Особенности внешней сортировки
 

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

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

1. Считать все записи из файла в оперативную память.
2. Произвести сортировку записей файла в оперативной мяти.
3. Записать отсортированные записи в файл.

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

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