ленты в прямом направлении, а остальные ленты - в обратном. Этим завершается сортировка; результат находится на ленте q в порядке возрастания.

83. [Начать новый уровень.] Установить ll+l,rq, s-iOuq-i{q+l) mod Т. Записать начальные серии на ленты (q + j) mod Г, где 1 < i < Т - 2. (Таким образом, начальные серии будут записаны на все ленты, кроме лент q и г.) Установить ки,д1 <--1 и A[i,r-] <--2.

84. [Можно ли выполнять слияние?] Если kU-l,q Ф s, вернуться к шагу ВЗ.

85. [Слияние.] (В этот момент k\.l-\,q\ = АО,Я = s при всех j ф q, j ф г.) Выполнить слияние на ленте г, читая в обратном направлении. (См. выше определение этой операции.) Затем установить s s -ь 1, i - 1, А[/, г] -«-в

и A[/,q] i--1. Установить г ( {2q - г) mod Т. (В общем случае имеем г =

{q - 1) mod Г, если s четно, и г = (q + 1) mod Г, если s нечетно.)

86. [Завершено ли формирование уровня?] Если I = О, перейти к шагу В2. В противном случае, если kU,jl = s для всех j ф q п j ф г, перейти к шагу В4. В противном случае вернуться к ВЗ.

Чтобы показать работоспособность этого алгоритма, можно использовать доказательства наподобие рекурсивной индукции так же, как для алгоритма 2.3.IT. Предположим, что мы начинаем с шага ВЗ при I = lo, q = qo, s+ = kUo, (Qo + I) modT] и s = kilo, (qo-l) modT]. Допустим, кроме того, что либо s+ = О, либо s = 1, либо s+ = 2, либо s- = 3, либо • •. Можно проверить по индукции, что алгоритм, в конце концов, придет к шагу В5, не изменив строки А с 0-й по о-ю. При этом будут получены следующие значения переменных: I = 1о + 1, q = qol, г = qo я s - s+. или s-. Причем выбирается знак "+] если s+ = О или {s+ = 2 и s Ф I), или (s+ = 4 и s- ф 1, 3), или • • •, и знак "-" - если (s- = I и s+ ф 0) или (s- = 3 и s+ ф О, 2), или • • •. Приведенный здесь "набросок" доказательства не очень элегантен, но ведь и сам алгоритм сформулирован в виде, который больше годится для реализации, чем для проверки правильности.

На рис. 78 показана эффективность алгоритма В, выраженная средним числом слияний каждой записи в зависимости от 5 - числа начальных серий, причем предполагается, что начальные серии приблизительно равны по длине. (Соответствующие графики для многофазной и каскадной сортировок приведены на рис. 70 и 74.) При подготовке рис. 78 учтено небольшое усовершенствование, упомянутое в упр. 3. Метод, некоторым образом связанный с рассмотренным и названный круговой сортировкой (gyrating sort), разработан Р. М. Карпом (R. М. Кагр). и основан на теории слияния в прямом порядке, приведенной в разделе 5.4.4. [См. Combinatorial Algorithms, edited by Randall Rustin (Algorithmics Press, 1972), 21-29.]

Прямое чтение. Схема осциллирующей сортировки, по-видимому, требует возможности чтения в обратном порядке, поскольку приходится где-то накапливать длинные серии. Тем не менее в работе М. А. Goetz, Ргос. AFIPS Spring Joint Сотр. Conf. 25 (1964), 599-607, найден способ вьшолнения осциллирующей сортировки с помощью только прямого чтения и простой перемотки. Предложенный метод в корне отличается от остальных схем, которые мы рассматривали в этой главе, по следующим причинам.

20 50 100 200

Начальные серии, S

500 1000 2000

Рис. 78. Эффективность осциллирующей сортировки, использующей метод алгоритма В и упр. 3.

a) Данные иногда записываются в начало ленты, причем предполагается, что данные, которые находятся на середине ленты, не разрушаются.

b) Все начальные строки имеют фиксированную максимальную длину.

Условие (а) нарушает свойство "первым включается - первым исключается" которое, как мы предположили, является характеристикой чтения в прямом порядке. Однако оно может быть надежно реализовано, если между сериями оставлять участок чистой ленты достаточной протяженности и если в нужные моменты пренебречь ошибками четности. Условие (Ь) оказывается до некоторой степени противоречащим эффективному использованию выбора с замещением.

Осциллирующая сортировка Гоетца (Goetz) с прямым чтением имеет одно сомнительное достоинство - это один из первых алгоритмов, который был запатентован как алгоритм, а не как физическое устройство [U. S. Patent 3380029 (1968)]; если это не удастся оспорить, то из факта патентования следует, что алгоритм нельзя использовать в программе без разрешения владельца патента. Метод Бенчера (осциллирующая сортировка с обратным чтением) был запатентован IBM несколькими годами позже. (Увы, мы являемся свидетелями конца эры, когда удовольствие от открытия нового алгоритма само по себе считалось достаточным вознаграждением! К счастью, осциллирующая сортировка не настолько уж хороша, чтобы из-за нее стоило ломать копья. Будем все-таки надеяться, что здравомыслящие ученые.

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

Центральная идея в методе Гоетца состоит в таком использовании лент, чтобы каждая лента начиналась с серии относительной длины 1, за которой следовала бы серия относительной длины Р, затем - Р -л т. д. Например, если Т = 5, то сортировка начинается следующим образом ("." указывает текущее положение головки чтения/записи на каждой ленте).

И так далее. Во время фазы 1 лента Т1 перематывается и одновременно на Т2 записываются исходные данные; затем перематывается Т2 и одновременно на ТЗ записываются исходные данные и т. д. В конце концов, когда исходные данные исчерпаны, начинают появляться фиктивные серии, и иногда необходимо вообразить, что они записаны явно на ленте полной длины. Например, если S = 18, то серии Al на Т4 и Т5 будут зафиксированы во время фазы 9; нам придется продвинуться вперед по Т4 и Т5 при слиянии с Т2 и ТЗ на Т1 во время фазы 10, так как надо добраться до серий Ai на Т4 и Т5 для подготовки к фазе 11. С другой стороны, фиктивная серия Ах на Т1 необязательно должна существовать явно. Таким образом, "конец игры" несколько замысловат.

Еще с одним примером применения этого метода мы встретимся в следующем разделе.