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