Двухпутевое упрощенное слияние

Алгоритм М. (Двухпутевое слияние)

Этот алгоритм осуществляет слияние двух упорядоченный файлов х₁, х₂, …, х_m и у₁, у₂, …, у_n в один файл z₁, z₂, …, z_m+n.

(Начальная установка) Установить i:=1, j:=1, k:=1.

(Найти наименьший элемент) Если х_i £ у_j, то перейти к шагу М3; в противном случае перейти к М5.

(Вывести х_i) Установить z_k:=х_i, k:=k+1, i:=i+1. Если i £ m, то возвратиться к шагу М2.

(Вывести у_j,…,у_n) Установить (z_k, …, z_m+n):=(у_j, …, у_n) и завершить работу алгоритма.

(Вывести у_i) Установить z_k:=у_i, k:=k+1, j:=j+1. Если j £ n, то возвратиться к шагу М2.

(Вывести х_i,…,х_m) Установить (z_k, …, z_m+n):=(х_i, …, х_m) и завершить работу алгоритма.

Эта простая процедура слияния наилучший вариант, если m» n. (Но если m гораздо меньше n, можно разработать гораздо более эффективные алгоритмы сортировки).

Рис. 5 Сортировка естественным двухпутевым слиянием

Можно заметить, что метод сортировки вставками – это есть слияние двух подфайлов, у одного из которого n=1! Следовательно, задачу сортировки можно свести к слияниям, сливая все более длинные подфайлы до тех пор, пока не будет отсортирован весь файл. Для ускорения процесса вставок, можно рассмотреть вставку нескольких элементов за раз (n>1), группируя их. Такой метод слияний – один из самых первых методов сортировки, предложенный в 1945 Джоном фон Нейманом и носит название естественное двухпутевое слияние.

Блок-схема, соответствующая алгоритму Е. (Подразумевается использование оператора GOTO)