Прямое слияние

Общий алгоритм сортировки слиянием.

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

Прямое слияние.

Алгоритм сортировки прямым слиянием является простейшим алгоритмом внешней сортировки, основанный на процедуре слияния серией. В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2^k.

Алгоритм сортировки простым слиянием:

1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.

2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.

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

4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл (Рис.1).

После выполнения i проходов получаем два файла, состоящих из серий длины 2i. Окончание процесса происходит при выполнении условия 2i>=n. Следовательно, процесс сортировки простым слиянием требует порядка O (log n) проходов по данным.

Признаками конца сортировки простым слиянием являются следующие условия:

1. длина серии не меньше количества элементов в файле (определяется после фазы слияния);

2. количество серий равно 1 (определяется на фазе слияния).

3. количество серий равно 1 (определяется на фазе слияния).

Рис.1 Пример сортировки прямым слиянием.