2015-06-04
518
Пусть в последовательном файле (ленте) имеется следующая информация:
31 42 09 29 37 01 12 06
Во внешних сортировках каждый проход состоит из фаз. В методе простого слияния существует 2 фазы: разделения и слияния. Для рассмотренного метода нужны 3 ленты. Исходная последовательность (А) разделяется на 2 ленты (В и С):
A: 31 42 09 29 37 01 12 06 –исходный файл
B: 31 42 09 29
C: 37 01 12 06
Затем выполняется фаза слияния: анализируются доступные на лентах В и С элементы и посылаются на ленту А в виде упорядоченных пар:
A: 31 37 01 42 09 12 06 29.
Теперь содержимое ленты А состоит из упорядоченных пар. Затем снова разделяется наполовину:
В: 31 37 01 42
С: 09 12 06 29.
Последовательность сливается в упорядоченные четверки.
А: 09 12 31 37 01 06 29 42.
Схематично метод простого слияния выглядит так:
