Немедленно получаем

8. СлияниеС {Ф, Ф, Ф)-{Ф} Конкретизация (6) и развертка

с использованием 5.3.1 (2) и 5.3.2 (2),

Теперь посмотрим на

9. СлияниеС {(nlxl) + , {п2х2) + /2, « + Л)

Упоряд {Слияние! {{nlxl) + fl, {п2х2) + + f2, n + N))

Конкретизация (6). Продвижение фильтров (6.6) приводит нас к

10. СлияниеС {{nlxl) + fl, {п2х2) -\-f2,n+ N)

{{nxl) 4- \fV e Слияние! {fl, {п2х2) + f2, N) и ynop{fl)} если xl < x2 {{nx2) + f2 \f2 e Слияние! {{nlxl +fl, f2, N) и Упор {f2)

иначе

{{nxl) + fl I e СлияниеС {fl, {п2х2) -(- f2, N)} если xl < x2 {{nx2) + f2 \f2 e СлияниеС {{nlxl) + f/, f2, Л/)} иначе

Свертка с 5.2.2(2) и (6).

Наконец нам остается рассмотреть другие основные случаи. Синтез рекурсий прост, и мы опускаем детали. Фактически, так как и (2 упорядочены, а Слияние! {fl,Ф,N), например, не переупорядочивает , можно продолжать использовать в этих случаях Слияние!, однако мы сочли более аккуратным написать

11. СлияниеС {{nlxl)+ f!, Ф,п + М)

<= {{пх!) + fllfl с= СлияниеС {fl, Ф, N)}

12. СлияниеС (Ф, {п2х2) + f2, n + N)

<= {{пх2) + f2 I f2 e СлияниеС <Ф, f2, N)}.

Так мы получаем алгоритм S3 {Сортировка Слиянием).

S3 Сорт {Ф){Ф} Сорт{{х}){{{!х)})

Сорт {Х1\]Х2) и СлияниеС {fl, f2[f!\]f2])

fleCopT(,Xn f2s= Сорт (X2)

СлияниеС (Ф, Ф, Ф) <= {Ф} СлияниеС {{nlxl) + , Ф, n + N)

{{пх1) +fl\flСлияниеС{fl, Ф, N)}

СлияниеС (Ф, {п2х2) + f2, п + N)

{{пх2) + 12 I f2 е СлияниеС (Ф, f2, N)} СлияниеС {{nlxl) + , {п2х2) + f2,n + N)

{{nxl) + fl\flG СлияниеС {fl, {п2х2) + /2, N)]

если xl < х2 {{пх2) + /2 i/2s СлияниеС {{nlxl) + , /2, Л)} иначе.

5.3.3. Сортировка Вставками из Р2. Если в алгоритме Р2 разбивать множество X не на XI [} Х2, а на л; + Z, то уравнение для главной рекурсии примет вид

1. Перест{х + Х)<= [j Слияние!{{{1х)}, f2, 1{{1х}}Цf2])

!2ев Перест (Х)

Конкретизация 5.3.1(11) и развертка с использованием 5.3.1(9).

Таким образом мы синтезируем Слияние!, получая новые уравнения

2. Слияние! {{{1х)}, Ф, п + Ф) {{{пх)}}

Развертка с использованием 5.3.1(14) и 5.3.1 (12)

3. Слияние! {{{1х)}, {п2х2) -f f2, /г + Щ

{{пх) + fl \fl е Слияние! (Ф, {п2х2) + f2, N)} и {{пх2) + /2 1/2 G Слияние! {{{1х)}, f2, N)}

Развертка с использованием 5.3.1(11).

Назовем этот модифицированный алгоритм перестановок Р2 и заметим, что уравнение 5.3.1(3) больше не требуется.

Р2 Перест {Ф) {Ф}

Перест {х + Х) U Слияние! {{{lx)},f,[{{lx)}Uf)]

fsnepeCT(X)

Слияние! (Ф, Ф, Ф) <= {Ф} Слияние! {{{1х)}, Ф, rt-f Ф)

<={{{пх)}} Слияние! (Ф, {п2х2) + f2,n + N)

<= {{пх2) -f / I / е Слияние! {Ф. f2, N)} Слияние! {{{1х)}, {п2х2) + f2,n + N)

{{пх) + f! \f! Слияние! (Ф, {п2х2)

+ /2, N)}

и {{nx2)+f2 \f2(Слияние! {{{!х)}, f2, N)}.

Чтобы получить Сортировку Вставками, как обычно, определим

4. Сорт {Х) Упоряд {Перест {X)),

где Перест теперь задаетсяР2. Мы ограничимся лишь наброском синтеза главной рекурсии; так, конкретизируя (4), получаем

5. Сорт{х-\-Х)<= и Упорчд{Слияние1{{{1х),!,[{{1х)}[}П))

f Перест(Х)

Развертка с использованием (1) и с внесением Упоряд внутрь объединения.

Как и в Сортировке Слиянием, можно произвести свертку с (4), потому что исследование фильтров позволяет переписать (5) как

6. Сорт {х-\-Х) и Упоряд {Слияние! {{{!х)}, f,

Упоряд {Перест {X))

[{{lx)}Uf]))

и Упоряд {Слияние! {{{!х)}, f, [{{!х)} U f ])

fsCopT(X)

Свертка с (4).

Теперь рассмотрим

7. СлияниеС {{Ох), IN) Упоряд {Слияние! {{Ох)), IN)) н, в частности,

8. СлияниеС {{{!х), {п2х2) + /2, « + N)

Упоряд(Слияние!{{{!х), {п2х2) + f2, п+ М)

. Продвижение фильтра (6.7) приводит нас к

9. СлияниеС {{{!х), (n2x2)-\-f2, n-\-N)

{{пх) + f Г I f! е Слияние! (Ф, {п2х2) + f2, N) и Упор{!!)} если X <.х2 {{пх2) +12 I !2 е Слияние! {{{!х)}, f2, N) и ynop{f2)} иначе

{{пх) + U I fl е СлияниеС (Ф), {п2х2) + f2, N)} если X <х2 {{пх2) + f2 1/2 е СлияниеС {{{!х)), f2, N)} иначе

Свертка с 5.2.2(2) и (7).

6 Зак. 1117