Внешняя сортировка

Рассмотренные методы сортировки были рассчитаны на то, что таблица целиком помещается в оперативной памяти и в любой момент открыт доступ к любому элементу таблицы. Внешняя сортировка отличается тем, что время доступа к данным на внешних носителях чрезвычайно велико по сравнению с временем доступа к оперативной памяти.

Предположим, что нужно отсортировать таблицу из 5000
R₁-R₅₀₀₀ записей, а в оперативную память помещается не более 1000 записей. Решение может быть следующим – начать с внутренней сортировки каждого из 5 отрезков по 1000 записей, а затем слить полученные сортированные отрезки. Такой процесс – внутренняя сортировка с последующим внешним слиянием – является основой многих методов внешней сортировки.

В качестве введения рассмотрим метод, который можно назвать сбалансированным двухпутевым слиянием. Метод использует 4 файла. В первой фазе упорядоченные отрезки, получаемые внутренней сортировкой, помещаются поочередно в файлы 1 и 2 до тех пор, пока не исчерпаются входные данные. Начальная фаза распределения отрезков размещает пять отрезков следующим образом:

Файл 1: R_{1 –} R₁₀₀₀; R_{2001 –} R₃₀₀₀; R_{4001 –} R₅₀₀₀

Файл 2: R₁₀₀₁ – R₂₀₀₀; R₃₀₀₁ – R₄₀₀₀

Файл 3: пусто

Файл 4: пусто

Затем файлы 1 и 2 вновь позиционируем на начало и сливаем отрезки с этих файлов, получая отрезки вдвое более длинные, чем исходные. Эти отрезки попеременно записываются в файлы 3,4. Отрезок R_{4001 –} R₅₀₀₀ в файле 1 не имеет пары для слияния в файле 2. Неявно добавим для создания такой пары в файл 2 фиктивный отрезок длины 0. После первого прохода слияния получим:

Файл 1: пусто

Файл 2: пусто

Файл 3: R_{1 –} R₂₀₀₀; R_{4001 –} R₅₀₀₀

Файл 4: R_{2001 –} R₄₀₀₀

Применив тот же алгоритм к файлам 3,4, в файлах 1,2 получим результат:

Файл 1: R_{1 –} R₄₀₀₀

Файл 2: R_{4001 –} R₅₀₀₀

Наконец, после последнего прохода в файле 3 получим R₁ – R₅₀₀₀, и сортировка завершена.

Аналогично можно рассмотреть 3-х и более – путевое слияние. Пусть для сортировки выделено N файлов. Разделим их на 2 части – в одной M файлов, в другой - N-M файлов. Распределим исходные отрезки по возможности более равномерно по M файлам первой части и выполним M-путевое слияние, помещая результат слияния поочередно в оставшиеся N-M файлов. Затем выполним N-M – путевое слияние, помещая результаты слияния в файлы первой части.