Алгоритм шага №3:
# * Создается пустой стек пар <индекс начала подмассива> <tex>-</tex> <размер подмассива>.# * Берется первый упорядоченный подмассив.# * Добавляется в стек пара данных <индекс начала текущего подмассива> <tex>-</tex> <его размер>.# При выполнении двух последующих правил выполняется процедура слияния текущего подмассива с предыдущими* Затем правило следующее.Если Пусть <tex>X, Y, Z- </tex> — размеры трёх длины верхних подмассивов трех интервалов, которые лежат в стеке, то:. Причем <tex>X</tex> – это последний элемент стека. # Повторяем пока выражение (<tex>Z > X + Y</tex> && <tex> Y + > X</tex>) не станет истинным # Если количество элементов в стеке не меньше 3 и <tex>Z \leqslant X + Y </tex> – сливаем <tex>Y</tex> c <tex>min(X,Z)</tex> . Иначе Если одно из правил нарушается — массив <tex>Y\leqslant X </tex> сливается с меньшим из массивов – сливаем <tex>X</tex>, c <tex>ZY</tex>. Процедура повторяется до выполнения обоих правил или полного упорядочивания данных.Если остались не рассмотренные подмассивы, то берется следующий и переходим ко второму пункту# Возвращаемся в п. Иначе — конец1.
Основная цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке, а значит и размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.
