Сортировка файлов методом прямого слияния

Алгоритмы сортировки, рассмотренные ранее, неприменимы, если сортируемые данные расположены в файле с последовательным доступом (на диске), который характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному компоненту [1, 3, 9, 10, 13].

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

Метод заключается в следующем [3]:

1. Последовательность а разбивается на две половины: b ис.

2. Последовательности b ис сливаются при помощи объединения отдельных элементов в упорядоченные пары.

3. Полученной последовательности присваивается имя а, и повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются в упорядоченные четверки.

4. Предыдущие шаги повторяются: четверки сливаются в восьмерки и так далее, пока не будет упорядочена вся последовательность.

В качестве примера возьмем следующую последовательность

Об, 67

Первый шаг: разбиение дает две последовательности

Об, 67

Слияние в упорядоченные пары дает последовательность

44, 94, 18, 55', Об, 12', 42, 67