Информатика · объяснение и практика
Слияние отсортированных частей: два указателя и стабильность
Слияние двух готовых массивов: сравнение первых оставшихся элементов, обработка хвоста и правило стабильности при равенстве.

В теме Поиск и сортировка · Учебная карта
В маршруте Сортировки и сравнение строк · 10 тем
Главная мысль
Два отсортированных списка сливают двумя указателями. На каждом шаге берут меньший из первых ещё не использованных элементов. Когда один список заканчивается, остаток другого дописывают целиком. Для стабильности при равенстве выбирают элемент из левой исходной части.
Почему достаточно смотреть на начало остатка
Внутри каждой части значения уже расположены по возрастанию. Значит, её первый ещё не взятый элемент не больше остальных в той же части. Чтобы выбрать наименьший элемент среди обоих остатков, достаточно сравнить только эту пару начал. Повторный просмотр всех чисел не требуется.
После выбора сдвигают указатель только в том списке, откуда взяли элемент. Если передвинуть оба указателя, одна запись потеряется. Если не сдвинуть нужный указатель, одна запись появится повторно. У результата на каждом шаге есть проверяемое свойство: он отсортирован и содержит ровно уже потреблённые записи.
Соединяем списки с одинаковыми ключами
Пусть левая часть содержит 2 А, 7, 9, а правая — 2 Б, 4, 10. Сначала сравниваются две двойки. Если левая часть действительно предшествовала правой в исходных данных, стабильный вариант должен взять А раньше Б. Затем выбираются Б, четвёрка, семёрка и девятка.
После девятки левая часть закончилась. Десятку дописывают без дальнейших сравнений с отсутствующим левым элементом. Завершение одного остатка является обычным случаем алгоритма, а не ошибкой. То же правило действует, если одна часть была пустой ещё до первого сравнения.
Пример
Слияние [2 А,7,9] и [2 Б,4,10] даёт [2 А,2 Б,4,7,9,10].
На равенстве выбирается левая запись. Затем каждый шаг удаляет ровно одно начало остатка; после исчерпания левого списка остаётся дописать 10.
Один этап слияния и полная сортировка
Если суммарно имеется n элементов, каждый из них переносится в результат один раз. Для двух непустых частей требуется не более n−1 сравнения ключей: последний остаток уже не с чем сравнивать. Затраты на само слияние линейны, если сравнение и перенос одного элемента имеют постоянную стоимость.
Сортировка слиянием сначала получает готовые части рекурсивным делением, а затем использует эту процедуру на разных уровнях. Для обычного массива с отдельным буфером требуется дополнительная память. Утверждение «слияние линейное» не означает, что полная сортировка произвольного массива тоже линейна: уровней объединения несколько.
От чтения к действию
А теперь — вы
Частые вопросы
Можно сливать неотсортированные части тем же правилом?
Алгоритм выполнится, но отсортированный итог не гарантируется: его доказательство опирается на готовность обеих частей.
Почему при равенстве выбирают левую запись?
Если левая часть раньше стояла в исходном списке, такой выбор сохраняет взаимный порядок равных ключей.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Сортировка вставками: как элемент находит место в готовом префиксе
Сортировка вставками на небольшом списке: готовый префикс, сдвиги больших элементов и сохранение порядка одинаковых значений.
Открыть темуРазбиение около опорного: что гарантирует один шаг быстрой сортировки
Что делает разбиение около опорного элемента: области меньше, равно и больше, их инварианты и границы обещания одного шага.
Открыть тему