каждой пересылки элемента. Если же они пересылаютр в верхний конец массива, то индексом пересылки является и / после каждой пересылки уменьшается на 1. Чтобы упрц стить операцию слияния, мы будем считать, что место пере сылки всегда обозначается через к, и будем менять местац!, значения k п I после слияния каждого р-набора, а прираще, ние индекса обозначим через Л, где h равно либо 1, либо Уточнив таким образом конструкцию , мы получаем

h :~ I; т := п; [т-номера сливаемых элементов] repeat q := р; г :=: р; т :- т-2*р;

слияние q элементов из / и г элементов из j, индекс засылки есть к с приращением / >; (2-22) h := -Л; -обмен знячештт^У[1

(2.23)

until m = О

На следующем этапе уточнения нужно сформулировать саму операцию слияния. Здесь следует учесть, что остаток подпоследовательности, которая остается непустой после слияния, добавляется к выходной последовательности при помощи простого копирования.

While fe?£:0) Л (Г^О) do begin [выбор элемента из i или j] if aii] .key < a[j] .key then

begin пересылка элемента из / в ft;

увеличение / и к ; q := q-l end else

begin пересылка элемейта ro J в к, увеличение j и /г ; г / -1

end;

копирование остатка последовательности г ; кошгрование остатка последовательности у

После уточнения операций копирования остатков программа будет ясна во всех деталях. Перед тем как записать ее полностью, мы хотим устранить ограничение, в соответствии с которым п должно быть степенью двойки. На какуо часть алгоритма это повлияет? Легко убедиться в том, что в более общей ситуации лучше всего использовать прежнк метод до тех пор, пока это возможно. В данном случае это означает, что мы продолжаем слияние р-наборов, пока длкнэ остатков входных последовательностей не станет меньше Р-Это влияет только на ту часть, где определяются значеШЗ

длины последовательностей, которые предстоит слить.

Сесто трех операторов

q.= p; г:=р; т:-т -2*р

пользуются следующие четыре оператора, и, как может бедйться читатель, здесь эффективно применяется описанная У ще стратегия; заметим, что m обозначает общее число эле-рнтов в двух входных последовательностях, которые осталось слить:

if т^р then q:=p e!se q:-tn; m:==tn-q;

if m>p then r:=p else r:=m; m:==m -r,

Й наконец, чтобы обеспечить окончание работы программы, нужно заменить условие р = п, управляющее внешним циклом, на р' п. После этих модификаций мы можем попытаться описать весь алгоритм в виде законченной программы (см. программу 2.13).

Анализ сортировки слиянием. Поскольку на каждом проходе р удваивается и сортировка заканчивается, как только р^п, она требует [log2nj проходов. По определению при каждом проходе все множество из п элементов копируется ровно один раз. Следовательно, общее число пересылок равно

М = п-[loga ] (2.24)

Число С сравнений по ключу еще меньше, чем М, так как при копировании остатка последовательности сравнения не производятся. Но, поскольку сортировка слиянием обычно применяется при работе с внешними запоминающими устройствами, стоимость операций пересылки часто на несколько порядков превышает стоимость сравнений. Поэтому подробный анализ числа сравнений не представляет особого практического интереса.

Алгоритм сортировки слиянием выдерживает сравнение даже с усовершенствованными методами сортировки, которые обсуждались в предыдущем разделе. Но затраты на управление индексами довольно высоки, кроме того, существенным недостатком является использование памяти размером 2п элементов *\ Поэтому сортировка слиянием редко применяется при работе с массивами, т. е. данными, расположенными в оперативной памяти. Цифры, характеризующие бы-*стродействие сортировки слиянием в режиме реального вре-Чени, содержатся в последних строках табл. 2.9 и 2.10. Эти Показатели лучше, чем у пирамидальной сортировки, но хуже, У^быстрой сортировки.

р *) Напомним, что в итеративном варианте алгоритма быстрой сорти-зи требуется стек размера п, а в рекурсивном варианте затраты памяти Чителыю больше. - Прим. ред.

procedure wfy-gtjof г;

таг ijjc,l,t: index;

h,m,p,q,r: integer; up: boolean; [a шеет индексы J,.. . ., 2*и) ibegfn up := true; p:== T; ►

repeat A := 1; m- :== и; if up then

hcgin / := 1; j n; к := и+1; / := 2*n end else

begin к := 1; / :=> и; i := n+1; J :== 2*n . end ;

3-epeat [слияниесерий usinj-ak]

- tmnHffcftnal, r ~ длм в ce/uu из>]

it m> p then q : p else q m; m w-fii;

it m > p then r := p else r := wi := w-r;

whUe (9:?t0) Л (rO) do

begin [слияние]

if И .Aey < D1 t > then

begin a[k]:- a[i]; к := k+h; i i+l; q : e-t

begin [1 a[j]; к := k+h; J J-l; r r-l end end ;

[копирование остатка серии из j] while г О do

begin alk] := [у]; к := Л+Л; / := г := r-l

end ;

[копирование остатка серии из i] while q О йо

begin alk] := И; А:: k+h; ii t+U 9

end ;

A := -A; < := Л; A: :=/; / := / until 7И = 0

up :- -aip; p := Ър

until p n;

it -lup then

fc-r j :== 1 to n do i] := end [mergesort]

Программна 2.13. Сортировка простым слиянием.