Когда двигать указатели при слиянии массивов

Условие

Два отсортированных массива нужно слить, сохраняя повторы. Указатели i и j стоят на первых необработанных элементах. Как выбирать следующий и что делать при равенстве?

Ответ

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

После исчерпания одного массива допишите оставшийся хвост другого. Условие основного цикла: оба указателя находятся внутри своих массивов. Каждый элемент добавляется один раз, время O(n+m), память результата O(n+m). Для стабильного слияния заранее определите порядок равных элементов разных источников.