- Zl

Z2

Z3

Z4

Zf,

ze

Z7

ZS

zg

Zio

Zll

Рис. 48. Четно-нечетное слияние для m = 4 и n = 7.

нулей с последующими единицами. Решающим моментом доказательства является то, что

([А;/21 + R/21) - {[к/2\ + [1/2}) = О, 1 или 2. (3)

Если эта разность равна О или 1, то последовательность (2) уже упорядочена, а если она равна 2, то одна из операций сравнения-обмена в (1) ставит все на свои места. Доказательство завершено. (Заметим, что принцип нулей и единиц сводит С"") случаев в задаче слияния всего лишь к {т+ 1)(п + 1) случаям, каждый из которых представляется двумя параметрами - к и I.)

Пусть С{т,п) - число модулей компараторов, используемых при четно-нечетном слиянии т- и п-элементов, не считая начальных тп- и п-сортировок; имеем Г тп, если тп < 1;

() = [с{\т/2],1п/2])-ьС{[т/2\,[п/2})-ь[{т+п-1)/2\, если тп > 1.

В общем случае это не слишком простая функция от m и п, однако, заметив, что С(1, п) = п и что

С(т-f-1, п-Ы) - С(т, п)

= 1 + C([m/2J -f-1, [n/2J + 1) - C(Lm/2j, [n/2J), если тп > 1,

мы можем вывести соотношение

C(m-f-l,n-f-1)-C(m,n) = [IgmJ-f-2-f-Ln/2L8"J+iJ, если n > m > 1. (5) Следовательно,

C{m,m + r) = B{m)-\-m-\-Rm{r) при m > 0 и r > 0, (6)

где B{m) = XfcLiTlgl - это функция "бинарной вставки" из соотношения 5.3.1-(3), а Rmir) обозначает сумму первых m членов ряда

Если же r = 0, получаем важный частный случай

C(m, m) = В{т) -f- m.

Кроме того, если t = [Igm], то

Rmir + 2*) = Rm{r) -h 1 • 2*-i + 2 • 2*-2 + = Rm{r)-h m + t 2-\

(7) (8)

+ 2*-i • 2° + m

Следовательно, С{т, п + 2) - С{т, п) имеет простой вид и

С{т,п) = + ) + (1) при фиксированном т, п -> оо, f = [Igm]; (9)

член 0(1) становится, в конце концов, периодической функцией от п с периодом 2. Асимптотически при п -> оо величина С{п,п) = nlgn + 0(п), как следует из (8) и упр. 5.3.1-15.

Сети с минимальным числом сравнений. Пусть §{п) - минимальное число сравнений, требуемых в сети сортировки для п элементов; ясно, что 5(п) > 5(п), где 5(п) - минимальное число сравнений, необходимое для сортировки безо всяких ограничений (см. раздел 5.3.1). Мы видели, что 5(4) = 5 = 5(4), поэтому новое ограничение не приведет к потере эффективности при п = 4; но уже при п = 5 оказывается, что 5(5) = 9, в то время как 5(5) = 7. Задача определения 5(п) кажется еще более трудной, чем задача определения 5(п); до сих пор неизвестно даже асимптотическое поведение 5(п).

Интересно проследить историю поиска путей решения этой задачи, так как каждый новый шаг стоил определенных усилий. Сьти сортировки были впервые исследованы Ф. Н. Армстронгом (Р. N. Armstrong), Р. Дж. Нельсоном (R. J. Nelson) и Д. Дж. ОКоннором (D. J. OConnor) около 1954года [см. U.S. Patent 3029413]. Как. сказано в их патентной заявке, "приложив старания, можно сконструировать экономичные п-входные сортирующие переключатели с помощью уменьшенного чнша двухвходовых сортирующих переключателей" Показав, что 5(п + 1) < 5(п) + п, они предложили специальные конструкции для 4 < п < 8, использовав соответственно 5, 9, 12, 18 и 19 компараторов. Работая далее над этой задачей, Нельсон совместно с Р. Ч. Бозе (R. С. Bose) задались целью показать, что 5(2") < 3" - 2" при всех п; следовательно, 5(п) = O(ns) = 0{п). Бозе и Нельсон опубликовали свой интересный метод в JACM 9 (1962), 282-296, гдо ихсказали предположение, что это наилучший возможный результат; Т. И. Хиббард (Т. N. Hibbard) в JACM 10 (1963), 142-150, описал аналогичный, но более простой метод, в котором используется такое же число сравнений, подкрепив тем самым это предположение.

В 1964 году Р. У. Флойд (R. W. Floyd) i! Д. Э. Кнут использовали новый подход к этой задаче, приведший к асимптотической оценке вида 5(п) = 0(n+/°s"). Независимо К. Э. Бэтчер (К. Е. Batcher) разработал описанную выше общую стратегию слияния. Используя компараторы, число которых определяется рекурсивным выражением

с(1)=0, c(n)=:c([n/21)+c(Ln/2j)+0([n/2l,Ln/2j) при п > 2, (10) он доказал, что (см. упр. 5.2.2-14)

c(2) = (t2-i + 4)2-2 i.

следовательно, 5(п) = 0(n(logn)). Как Бэтчер, так и Флойд с Кнутом опубликовали свои конструкции лишь через некоторое время [см. Notices of the Amer. Math. Soc. 14 (1967), 283; Proc. AFIPS Spring Joint Computer Conf 32 (1968), 307-314].

Кое-кому удалось сократить число компараторов, используемых в конструкции слияния с обменами, предложенной Бэтчером. В (11) показаны наилучшие из известных в настоящее время верхних оценок для 5(п.).

n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 c(n) = 0 1 3 5 9 12 16 19 26 31 37 41 48 53 59 63 (11)

5(n) < 0 1 3 5 9 12 16 19 25 29 35 39 45 51 56 60

Так как 5(n) < c(n) при 8 < n < 16, обменная сортировка со слиянием неоптимальна при всех п > 8. Если п < 8, то такая сортировка эквивалентна по количеству компараторов конструкции Бозе и Нельсона. Флойд и Кнут доказали в 1964-1966 годах, что указанные значения 5(п) точны при п < 8 [см. А Survey of Combinatorial Theory (North-Holland, 1973), 163-172]; значения 5(n) при n > 8 до сих пор неизвестны.

Конструкции, позволившие получить указанные выше значения (см. (11)), представлены графически на рис. 49. Сеть при п = 9, основанная на интересном трехпутевом слиянии, была построена Р. У. Флойдом в 1964 году; установить ее корректность можно при помощи общего принципа, описанного в упр. 27. Сеть при п = 10 построил в 1969 году А. Ваксман (А. Waksman); он рассматривал входы как перестановки множества {1,2,..., 10} и пытался, сохраняя некоторую симметрию, насколько возможно уменьшить число значений, которые могут появляться в каждой строке на данной стадии.

Представленный вариант сети для п = 13 построен по довольно отличающейся технологии: Хью Жуиле (Hugues Juille) разработал программу, чтобы построить эту сеть, моделируя эволюционный процесс размножения [Lecture Notes in Сотр. Sci. 929 (1995), 246-260]. Сеть имеет несколько необычный вид, но она работает; к тому же она меньше других сетей, созданных рациональным человеческим разумом.

В 1969 году Дж. Шапиро (С. Shapiro) нашел сеть сортировки 16 элементов с 62 компараторами, и это было весьма неожиданно, поскольку результат, полученный методом Бэтчера (63 сравнения), казалось, невозможно улучшить, если п является степенью 2. Познакомившись с конструкцией Шапиро, в еще большее изумление поверг всех М. У. Грин (М. W. Green), который нашел сортировку с 60 сравнениями, показанную на рис. 49. Первая часть конструкции Грина довольно проста для понимания; после того как вьшолнены 32 операции сравнения-обмена слева от пунктирной линии, все прямые можно так пометить 16 подмножествами {a,b,c,d}, чтобы о прямой, помеченной s, было известно, что она содержит числа, меньшие или равные содержимому прямой, помеченной t, всякий раз, когда s есть подмножество t. - Состояние сортировки на этой стадии более подробно рассматривается в упр. 32. Однако сравнения, выполняемые на последующих уровнях сети Грина, становятся совершенно загадочными. До сих пор никто не знает, как обобщить эту конструкцию, чтобы получить столь же эффективные сети для больших значений п.

Шапиро и Грин создали также изображенную на рис. 49 сеть для п = 12. Хорошие сети для п = 11, 14 или 15 можно получить, удалив нижнюю линию в сети для п -f-1 вместе со всеми компараторами, подсоединенными к этой линии.

Наилучшая известная к настоящему моменту сеть для 256 элементов, разработанная Д. Ван Борисом (D. Van Voorhis), свидетельствует, что 5(256) < 3651 по сравнению с 3839 в сети, которая построена по методу Бэтчера. [См. R. L. Drysdale, F. Н. Young, SICOMP 4 (1975), 264-270.] При п оо оказывается, что 5(п) = 0(пlogп); эта впечатляющая верхняя оценка найдена Айтаи (Ajtai), Комлошем (Komlos) и Шемереди (Szemeredi) в Combinatorica 3 (1983), 1-19. Построенные ими сети не представляют практического интереса, поскольку множество компараторов