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

Частичная сортировка (слияние)


Вторым направлением исследования частичной сортировки является задача слияния двух отсортированных таблиц

и

в одну отсортированную таблицу

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


Алгоритм 15.5. Прямое слияние


Содержание раздела