5.3. Каскадное слияние
При каскадном -ленточном слиянии налентах первоначально находится в общем случае разное количествоупорядоченных серий с длинами.
Слияние происходит за несколько этапов. На каждом этапе последовательными слияниями (по одной серии с каждой ленты) опустошается очередная лента (с минимальным числом серий). Лента с новыми, уже более длинными сериями не участвует в дальнейших слияниях вплоть до завершения прохода по всем данным. Длина новой серии равна сумме длин серий на участвующих лентах. Поскольку число участвующих лент последовательно уменьшается, убывает и длина новой, «слитой» серии.1
Пример. Пусть в слиянии участвует лент. Значком
будем обозначать, что в текущий момент на ленте находитсясерий длины; пустую ленту обозначает значок
Ленты, не участвующие в дальнейших слияниях вплоть до завершения прохода по всем данным, помечены «*».
Исходное расположение серий на лентах:
Рис. 31
Общее количество элементов на лентах, таким образом, выражается числом .
Шаг 1. Опустошение ленты с минимальным числом серий. После того, как ленту будет слито по одной серии, на ней окажется одна серия диной, а на первых четырёх лентах число серий уменьшится на единицу:
Рис. 32.
После слияния ещё одной четвёрки серий на ленту получится следующее распределение серий:
Рис. 33.
Закончится первый шаг после ещё одного слияния распределением:
Рис. 34.
Шаг 2. Опустошение ленты . Слияние теперь производится на ленту . Длина возникающих на ней серий равна. Серии лентыв дальнейших слияниях не участвуют. Аналогично первому шагу придём к распределению (промежуточные слияния не отображаем):
Рис. 35.
Шаг 3. Опустошение ленты . Слияние теперь производится на ленту . Длина возникающих на ней серий равна. Серии лентыи лентыв дальнейших слияниях не участвуют. Аналогично предыдущему придём к распределению:
Рис. 36.
Первый этап окончен — завершён проход по всем данным. Свободна лента . Остальные ленты готовы ко второму этапу.
Второй этап сопровождается следующими распределениями серий (показаны ситуации опустошения очередной ленты):
Рис. 37.
Рис. 38.
В результате на ленте оказывается полностью отсортированный массив изэлементов.
Рис. 39.
Если ставится цель, чтобы в последнем слиянии на пустую ленту участвовали все остальные ленты, по одной серии на каждой (так что они опустошаются разом), то приходим к так называемому точному начальному распределению серий. Отправляясь от желаемого конечного распределения (длины серий не важны) получаем перед очередным проходом по всем данным (пустая лента не показана, номера лент с указанным числом серий могут не совпадать с номером столбца в таблице — важно распределение серий):
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
4=1+1+1+1 |
3=1+1+1 |
2=1+1 |
1 |
10=4+3+2+1 |
9=4+3+2 |
7=4+3 |
4 |
30=10+9+7+4 |
26=10+9+7 |
19=10+9 |
10 |
… |
… |
… |
… |
a |
b |
c |
d (a>b>c>d) |
a+b+c+d |
a+b+c |
a+b |
a |
Последняя строка таблицы означает, что если на каком-либо «ретроспективном» шаге имеем распределение серий по лентам
,
то после очередного прохода по всем данным придём к распределению .
1В убывании числа участвующих лент и заключается «каскадность» слияния.