Same-Direction Pointers

Два отсортированных списка нужно объединить в один. В лоб: склеить и отсортировать — $O((n+m)\log (n+m))$, хотя оба входа уже упорядочены и вся работа сортировки уходит впустую. Пересечь два списка перебором — и вовсе $O(nm)$.

Вторая половина задач — про запись: удалить дубликаты, перенести нули в конец, отфильтровать элементы по условию. Очевидное решение создаёт новый массив, то есть $O(n)$ дополнительной памяти, которой на больших данных может просто не быть.

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

i = j = 0
out = []

while i < len(a) and j < len(b):
    if a[i] <= b[j]:            # <= сохраняет стабильность
        out.append(a[i]); i += 1
    else:
        out.append(b[j]); j += 1

out.extend(a[i:])               # ровно один из хвостов непустой
out.extend(b[j:])
return out

• Время — $O(n+m)$: каждый элемент обрабатывается один раз.
• Память — $O(n+m)$ на результат при слиянии и $O(1)$ при записи на месте.
• Инвариант слияния: в out уже лежат все элементы, меньшие обоих текущих; минимум оставшихся — это a[i] или b[j].
• Инвариант записи: write <= read, поэтому запись не портит ещё не прочитанное.

Оба массива упорядочены, значит минимум из всех необработанных элементов обязательно стоит на одном из двух указателей: внутри каждого массива всё остальное больше. Выбирая меньший из a[i] и b[j], мы каждый раз добавляем в ответ действительно минимальный оставшийся элемент — этого достаточно, чтобы результат оказался отсортированным.

В задачах записи корректность следует из неравенства write <= read, которое сохраняется на каждом шаге: пишущий сдвигается не чаще читающего. Значит, ячейка, в которую мы пишем, либо уже прочитана, либо это та же ячейка, что и читаемая, — потерять данные невозможно.

Прикладная версия того же приёма — merge join в базах данных и пересечение постинг-списков в поиске: два отсортированных потока, два курсора, один проход. Отличие только в том, что данные приходят с диска, а не из памяти.

• Забытые хвосты. После основного цикла один из массивов почти всегда не исчерпан.
• Слияние на месте слева направо. Запись затирает ещё не прочитанные элементы; идти нужно с конца.
• Потеря стабильности. < вместо <= меняет порядок равных элементов — для сортировки по нескольким ключам это ошибка.
• Дубликаты при пересечении. Если в обоих списках есть повторы, нужно решить, сколько раз элемент попадает в ответ, — и сдвигать указатели соответственно.
• k списков попарно. Слияние по одному даёт $O(kN)$; куча по головам даёт $O(N\log k)$.

1. Почему после основного цикла слияния достаточно дописать оба хвоста, не проверяя, какой именно непустой?
2. Слияние на месте в массив с запасом: с какого конца идти и почему?
3. Удаление дубликатов на месте: что означает значение write в конце работы?
4. Пересечение двух отсортированных списков с повторами — сколько раз элемент должен попасть в ответ и как это обеспечить?
5. Когда выгоднее не сливать, а искать бинарным поиском?