Алгоритмы сортировки, рассмотренные ранее, неприменимы, если сортируемые данные расположены в файле с последовательным доступом (на диске), который характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному компоненту [1, 3, 9, 10, 13].
Основной применяемый метод — сортировка слиянием. Слияние означает объединение двух (или более) последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Одна из сортировок на основе слияния называется сортировкой простым слиянием.
Метод заключается в следующем [3]:
1. Последовательность а разбивается на две половины: b ис.
2. Последовательности b ис сливаются при помощи объединения отдельных элементов в упорядоченные пары.
3. Полученной последовательности присваивается имя а, и повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются в упорядоченные четверки.
4. Предыдущие шаги повторяются: четверки сливаются в восьмерки и так далее, пока не будет упорядочена вся последовательность.