Таблица 1

ПРИБЛИЗИТЕЛЬНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ КАСКАДНОГО СЛИЯНИЯ

(Т - 1)-путевое слияние в то время как каскадная использует (Т - 1)-путевое, (Т - 2)-путевое, (Т - 3)-путевое и т. д. В действительности же для шести и более лент каскадная схема асимптотически лучше, чем многофазная. Как мы видели в разделе 5.4.2, высокий порядок слияния не является гарантией эффективности. В табл. 1 показаны характеристики выполнения каскадного слияния по аналогии с подобной таблицей из раздела 5.4.2.

Нетрудно, рассуждая "в обратном направлении" от конечного состояния (1,0, ...,0), вывести "точные распределения" для каскадного слияния. В случае для шести лент имеем следующее.

Отметим интересное свойство этих чисел - их относительные величины являются также и длинами диагоналей правильного {2Т - 1)-угольника. Например, пять диагоналей одиннадцатиугольника на рис. 73 имеют относительные длины, очень близкие к 190, 175, 146, 105 и 55! Мы докажем ниже в этом разделе такой замечательный факт и увидим, что значения относительного времени, затрачиваемого на (Т - 1)-, {Т - 2)-, ..., 1-путевое слияние, приблизительно пропорциональны квадратам длин этих диагоналей.

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

Рис. 73. Геометрическая интерпретация каскадных чисел.

полные проходы. Если имеется 190 начальных серий, то каждая запись обрабатывается пять раз, как в приведенном выше примере, но если имеется 191 серия, то, очевидно, следует увеличить уровень. Теперь каждая запись будет обрабатываться шесть раз. К счастью, на практике можно избежать такого резкого скачка. Дэвид Э. Фергюсон (David Е. Ferguson) сумел так распределить начальные серии, что многие операции во время первой фазы слияния свелись к копированию содержимого ленты. Обойдя такие копирования (просто изменив "логические" номера ленточных устройств по отношению к "физическим" номерам, как в алгоритме 5.4.2D), получим относительно плавный переход от одного уровня на другой, как изображено на рис. 74.

Предположим, что {a,b,c,d,e), где a>b>c>d>e - точное распределение. Изменив соответствие между логическими и физическими ленточными устройствами, можно представить, что реальное распределение - {e,d,c,b,a), т. е. а серий на Т5, b - на Т4 и т. д. Следующее точное распределение - это {a + b + c + d + e, a + b+c+d, a + b + c, a + b, a); если же ввод исчерпывается прежде, чем мы достигаем этого следующего уровня, будем считать, что на лентах содержится соответственно (Dl,1)2,1)3,1)4,5) фиктивных серий, где

Di<a + b + c+d, D2<a + b + c, D3 < а + b, D4 < а, d5 = 0;

Di>D2>D3>D4> Db. (2)

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

1. Если Di = а, то вычесть а из всех Di, D2, D3, D4 и заявить, что Т5 - результат слияния. Если D4 < а, то произвести слияние а серий с лент Т1 по Т5, используя минимально возможное число фиктивных серий на лентах от Т1 до Т5

7-»4

Г = 5

Г = 8 Г=10

10 20 50 100 200

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

500 1000 2000

5000

Рис. 74. Эффективность каскадного слияния с распределением по алгоритму D.

так, чтобы новые значения Di, D2, d3, D4 удовлетворяли соотношениям

£>i<6 + c + d, D2<b + c, Въ<Ь, £)4 = 0; Di > >-С»з >-С»4. (3)

Таким образом, если Di было первоначально < 6 + с, ни одна фиктивная серия с этой ленты на данном шаге не используется. В то же время, если 6+с < D2 < а+6+с, используется ровно D-b- с фиктивных серий.

2. (Этот шаг аналогичен шагу 1, но с некоторым "сдвигом".) Если D = 6, то вычесть Ь из всех Di, D2, Dsn объявить, что Т4 - результат слияния. Если D3 < Ь, то слить b серий с лент Т1-Т4, уменьшая, если необходимо, число фиктивных серий, чтобы достичь

Di<6 + c, D2<b, D3 = 0; I>i > i?2 >-Da-

3. И так далее.

Метод распределения серий по лентам Фергюсона можно проиллюстрировать, рассмотрев переход с уровня 3 на уровень 4 в (1). Допустим, что на "логических" лентах (Т1,..., Т5) содержалось соответственно (5,9,12,14,15) серий и что необходимо довести это количество до (55,50,41,29,15). Данная процедура кратко описана в табл. 2. Сначала помещаем девять серий на Т1, затем (3,12) - на Т1 и Т2 и т. д. Если ввод исчерпывается, скажем, на шаге (3, 2), то "сэкономленная величина" составляет 15 -f- 9 -Ь 5. Это означает, что мы избавляемся от пятипутевого слияния