Более точно,

б. Слияние {II, f2) {f \ f s[06pa3{fl)[j 06pa3{f2)] X Образ{fl)\j Образ{f2) и Биект {f,[06pa3{fl)[i Образ {f 2)], Образ {fl)

и Образ if 2))

и Peгyляp{f, fl) и Peгyляp{f, f2)},

6. Peгyляp{f, fl)Yxl, х2 Образ {fl)-

{fl)-\xl)<{fl)-{x2) =f~{xl)<f-{x2).

Далее в разд. 6.4 мы увидим, откуда возникает это сужение Перест.

Чтобы получить Перест {Х1\}Х2), уже недостаточно рассматривать произвольные fl Перест{Х1), f2 Перест{Х2). Необходимо взять все такие и f2, т. е.

7. Перест{Х1\}Х2) U Слияние{11, f2)

fl тПерест(Х1) 2 Перест (XS)

Это уравнение, конечно, нуждается в обосновании, но мы дадим его (неформально) позже, когда поймем, откуда берется фильтр Регуляр.

Необходимо построить рекурсию для Слияния. Вначале обобщим (5), определив

8. Слияние! {fl, f2, N){f \f S N X Образ {fl) U Образ {f2)

и Биект {f, N, Образ {fl), Образ {f2))

и Регуляр {f, fl) и Регуляр if, f2)},

и тогда

9. Слияние {fl, f2)-Cлuянuel{fl, f2, [Образ {fl)\] Образ {f 2)])

Сворачивая 5.3.1(5) с 5,3.1(8) Слияние {fl, f2, [flUf2]).

Сначала синтезируем главную рекурсию для Слияния!.

10. Слияние! {{nlxl) + , {п2х2) + /2, /г + Л)

{/ I f S п + X Образ {{п!х!) + fl)

и Образ {{п2х2) + !2) и Биект {f, n+N, Образ {{nlxl) + fl)

иОбраз{{п2х2) + 12))

и Регуляр {f, {nlxl)fl)

и Регуляр (/, {п2х2) -f f2)} Конкретизация (8).

Продвижение фильтра в этом случае сложнее, так как у нас имеются два фильтра. Детали приведены в разд. 6.4; в итоге(10) можно переписать как

<= {{пх1) + fl\flNX Образ (fl) и Образ {{п2х2) + /2) и Биект ifl, N, Образ if 1)

[}0браз{{п2х2) + !2))

и РегулярЦ!, /) и РегулярЦ!, {п2, x2) + f2)} и {{пх2) + !2 IfrNX Образ{{nlxl) + ) U Образ {f2) и Биект {12, N, Образ ({п1 х1)-\-fl)

и Образ (12))

и РегулярЦГ, {nlxl) + fl)

и Регуляр{12,12)} <= {{пх1) + fl I G Слияние] {fl, {п2х2) + f2, N)} и {{пх2) + f2 If2 G Слияние] {(nlxl) + fl, f2, N)}

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

Теперь осталось рассмотреть лишь основные случаи для Слияния]. Из уравнения (9) заметим, что когда впервые вызывается Cлuянuel{fl, f2, N), то Card(N)= Card{fl)+Cardiff), и из уравнения (11) мы видим, что при каждом рекурсивном вызове удаляется один элемент из iV и один из fl или f2, так что это соотношение сохраняется. Поэтому нам необходимо изучить основные случаи:

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

13. Слияние] {{nlxl) + fl, Ф, п +N){f \f п + N X Образ {fl)

и Об раз {Ф) и Биект {f, N, Образ {fl) U Образ (Ф)) и Peгyляp{f, {nlx])-\-f]) и Peгyляp{f, Ф)} Конкретизация 5.3.1(8).

Аналогичный случай возникает с fl = Ф. Для этих случаев можно снова построить рекурсию, однако синтез настолько прост, что мы его опускаем. Получаем

14. Слияние] {{nlxl) + fl, Ф, n + N)

<= {{п, xl)-\-f\fc= Слияние] {fl, Ф, N)}

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

{{пх2) + /1 / е Слияние] (Ф, f2, N)}.

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

Так мы получаем алгоритм Р2

Р2 Перест {Ф) <={Ф} Перест {{х}) {{{1х))}

Перест {Х1\}Х2)<= [] Слияние {fl, f2)

и Перест (XI) Перест (Л2)

Слияние {fl, f2) Слияние! {fl, f2, [fl [] f2]) Слияние! (Ф, Ф, Ф) {Ф} Слияние! {{nlxl) + f!,Ф, n-N)

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

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

{{пх1) + I G Слияние! {fl, {п2х2)

+ f2, N)} и {{пх2) + f2 \f2 е Слияние! {{nlxl)

+ fl, f2, N)}. 5.3,2. Сортировка Слиянием из Р2. Снова определим

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

где Перест получено из Р2 и Упоряд в 5.2.2(2). Отсюда немедленно получаем

2. Сорт{Ф) *={Ф} Конкретизация (1) и развертка

3. Сорт{{х}) -{{Ix}} Конкретизация (1) и развертка

4. Сорт {XI []Х2)<= и Упоряд {Слияние {fl, f2))

П%п7р17тш) Конкретизация (1), развертка с использованием 5.3.1(7) и внесение Упоряд внутрь объединения.

Исследование фильтров (6.5) позволяет нам переписать это как и У по ряд {Слияние {fl, f2))

ft е Упоряд (Перест (XD) Упоряд (Перест (Х2П

Таким образом, мы имеем

5. Сорт {Xl[jX2)<= и Упоряд {Слияние {fl, f2))

[5g°J(fn Свертка с (1).

Рассмотрев Упоряд {Слияние {fl, f2)), видим, что это есть Упоряд {Слияние! {fl, f2, [fl[jf2])), поэтому определим

6. CлuянueC{fl, f2, N) Упоряд {Слияние! {fl, f2, N)), и перепишем (5) в виде

7. Сорт {XI иХ2)<= и СлияниеС {fl, f2, [fl [] f2])

liicZrlxi] Развертка (5) с 5.3.1(9),

свертка с (6).