Естественное двухпутевое слияние – ЕДС

В обоих алгоритмах ЭДС и ФДС используется память объемом 2N. Попеременно одна область служит источником, а другая – получателем предупорядоченных последовательностей. В источнике одна предупорядоченная расположена слева направо, а другая справа налево (в конце). В каждый момент времени сравнивается очередные элементы подпоследовательностей (если они еще не пустые), и в результат записывается наименьший (наибольший из этой пары).

Естественная упорядоченность нарушается, если следующий за слитным элементом нарушил упорядоченность. В получателе меняется направление записи, а в источнике начинается новая пара упорядоченных подпоследовательностей. Это завершается если в источнике один и тот же элемент рассматривается с обеих сторон. После чего источник с получателем меняются ролями

_______ _____________

3 4 2 5 3 10 15 10 8 11 5 2

2 3 4 5 11 3 10 15 10 8 5 2

2 2 3 4 5 5 8 10 11 15 10 3

2 2 3 3 4 5 5 8 10 10 11 15

Наибольшее число операций выполняется при проверке ступеньки вниз, т.е. при выискивании упорядоченности. Чтобы отказаться от этих вычислений, фиксируем количество элементов слияемой последовательности: замечая, что последовательность из одного элемента упорядочена, объединяя такие последовательность, мы гарантированно получаем последовательность из двух элементов, а в следующий раз сливая из двух, получаем 4 элемента и т.д., кроме, быть может, последней подпоследовательности, если число элементов не является степенью 2.