Метод сбалансированного многопутевого слияния

Данный метод фактически исключает фазу разбиения, используя только фазу слияния. При этом в качестве выходных последовательностей, на которые переписываются элементы. Максимальное количество выходных файлов равно количеству серий последовательности. Количество последовательностей должно быть кратно двум.

Основные этапы:

1) Выбираются количество последовательностей.

2) Исходная последовательность разбивается на половину выходных последовательностей.

3) С выходных последовательностей, которые в данный момент фиксируется как входные; происходит слияние с соответствующей серией и их переписывание на вторую половину выходных последовательностей.

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

Пример. Сортировка с использованием 6-ти выходных последовательностей.

17 13 23 29 11 31 4 61 41 –2

выходные 1: 17 11 41 –4 входные

последовательности 2: 13 31 последовательности

3: 23 29 4 61 –2

4: 13 17 19 23 29 33 –4 выходные

5: 4 11 31 45 59 61 80 последовательности

6: –2 5 41 43

входные 1: –2 4 5 11 13 17 19... 61 80

2: –4

3: –

4: –4 –2... 80

5:

6: