/:=0; [1~число сливаемых серий)

- j = nh+ll [j-индекс выходной ленты)

repeat [слияние серий с t[l]... t[kl] на tU\)

kZ i.= l+l; [k2-число входных лент, -- участвующих-в слиянии)

tepsat [выбор наименьшего элемента) i := 1; тх := 1; min := /[(ф]]\.кеу-, while г < к2 йо

--begin i := i+l;x f[ta[i]]lkey;

it x< min then

begin min := x; mx := i

end ;

[наименьший элемент на ta[mx], пересылка его на tl/1) read(f[ta[mxlH, buf); eot := epf(f[ta[mxj\); тИе{ДШ, buf); If eot then

begin rewrite(f[ta[mx]]); [исключение ленты)

ta[mx] := ta[k2]; ta[k2] := ta[kl];

kl := kl-l; k2 := k2-l i

end else

if buf .key > f[ta[mx]]\ .key then begin tx := ta[mx]: 1фпх] := ta[k2]; ta[k2] :~ tx; k2 = k2-l

imtil k2 = 0;

iSjKn then j :== j+l elsejr := иА+1 nntU kl = 0; for 1 to л/г do

begin := ([/]; t[q :-= ф+лЛ]; ?[;+йя1 := /х end uotU / = 1;

eset(f[t[iW); И^1(/[Щ, t[l])t [отсортированный файл

находится на t[l]]

{tapemergesort] ;

и'в [формирование случайного файла /0} feng := 200; rand := 7789; rewriteifO); адгш£?:= (131071*ми mod 2147483647; . := rand div 2147484; write(fO, buf); leng fe/ii - I.

until feBg ==: 0;

set(fQ). listlfO, 1); , . .

emergesort .......

еще участвуют в игре. Очевидный прием - использовать сив булевских переменных, отражающих активность ц^ Однако мы предпочитаем другой метод, при котором бод^ эффективно работает процедура выбора, являющаяся в нечном счете наиболее часто повторяющейся частью алгп ритма. Вместо булевского массива вводится вторая карт лент ta. Эта карта используется вместо / так, что tall] ... /а[A2] - индексы лент, участвующих в работе. Итац. оператор (2) можно записать следующим образом:

(2.39)

к2 := kl;

repeat выбор минимального ключа, пусть ta[mx] - номер его ленты ; read(ta[mx]], buf);

--ytnteifmi hif);--

if ео/(/[<й[/ях]]) then исключение ленты else j

if buf.key > f[talmx]]1.key th n закрыть серию nntil fc2 = 0 i

Поскольку количество устройств-носителей магнитных! лент, доступных в вычислительной системе, обычно довольно! мало, алгоритм выбора, который нужно уточнить на следующем этапе, может также представлять собой простой линейный поиск. Оператор исключение ленты предиолагает уменьшение kl и k2, а также изменение значений индексов в карп ta. Оператор закрыть серию просто уменьшает А2 и должным образом переупорядочивает компоненты ta. Подробно, это показано в программе 2.15, которая является окончательным уточнением (2.37) при помощи (2.39). Заметим, что ленты освобождаются процедурой rewrite, как только прочитана последняя серия. Оператор переключение ленты разработан в соответствии сданными ранее пояснениями.

2.3.4. Многофазная сортировка

Теперь мы знаем необходимые приемы и подготовлены к тому, чтобы разработать и запрограммировать другой алгоритм сортировки, работающий более эффективно, чем алгоритмы сбалансированной сортировки. Мы видели, что при, сбалансированном слиянии устраняются операции просто! копирования, поскольку распределение и слияние объединены в' одну фазу. Возникает вопрос: можно ли еще лучш использовать имеющиеся ленты? Да, это действительно во.э-можно; очередное усовершенствование заключается в том, чтобы отказаться от строгого понятия прохода, т. е. использовать ленты более хитрым способом, чем тот, когда считаю! что всегда имеется N/2 входных лент и столько же выход-

меняют ролями входные и выходные ленты после йЬ1 j.Q отдельного прохода. При этом понятие прохода ста-тся нечетким. Этот метод был изобретен Р. Л. Гилстадом йОЧ и назван многофазной сортировкой.

вначале проиллюстрируем его на примере работы с тремя амИ- В каждый момент элементы сливаются с двух лент третью. Как только одна из входных лент окажется исчер-L.ff.....om сразу становится выходной лентой для слияния ой ленты, которая еще не исчерпана, и с той, которая до этого была выходной.

fl f2 f3

Рис. 2.14. Многофазная cop- Рис. 2.15. Многофазная сортировка слия-гаровка слиянием с тремя нием с шестью лентами, содержащими лентами, содержащими 21 65 серий,

Поскольку мы знаем, что п серий на каждой входной яенте .превращаются в п серий на выходной ленте, нам нужно только вести список числа серий на каждой ленте (вместо того, чтобы определять действительные ключи). На Ic. 2.14 предполагается, что вначале две входные ленты /1 /2 содержат соответственно 13 и 8 серий. Таким образом, Первом проходе 8 серий сливаются с /1 и /2 на /3, на fopoM проходе оставшиеся 5 серий сливаются с /3 и /1 /2 и т. д. В конце работы на ленте /1 содержится отсортированный файл. Второй пример демонстрирует многофазный метод лентами. Пусть вначале имеются 16 серий на /1, 15 -на *4 -на /3, 12 -на /4 и 8 -на /5; на первом частичном