Исправление monk, (текущая версия) :
В таком случае, не эффективно например, когда один из массивов из одного элемента - тогда проще поиском по сортированному массиву найти позицию вставки, чем перебирать все.
Если создавать новый, то быстрее параллельного обхода не придумаешь (всё равно каждый элемент надо читать и копировать).
Если не создавать (предположим, есть массив a длины N+M с заполненными M записями и массив b длины N, результат в массиве a), тогда можно перемещаться на следующий поиском.
i1 = позиция b[0] в a
перебираем k позиций из b, которые меньше a[i1+1]
i2 = позиция b[k] в a[i1+1:]
сдвигаем a[i1:] на k, вставляем найденный диапазон b[:k]
вставляем b[:k] в a[i2+k:] по этому же алгоритму
P.S. Алгоритм примерный, могут быть ошибки на плюс-минус один по позиции и не упомянуты проверки на конец массива.
Исходная версия monk, :
В таком случае, не эффективно например, когда один из массивов из одного элемента - тогда проще поиском по сортированному массиву найти позицию вставки, чем перебирать все.
Если создавать новый, то быстрее параллельного обхода не придумаешь (всё равно каждый элемент надо читать и копировать).
Если не создавать (предположим, есть массив a длины N+M с заполненными M записями и массив b длины N, результат в массиве a), тогда можно перемещаться на следующий поиском.
i1 = позиция b[0] в a
перебираем k позиций из b, которые меньше a[i1+1]
i2 = позиция b[k] в a
сдвигаем a[i1:] на k, вставляем найденный диапазон b[:k]
вставляем b[:k] в a[i2+k:] по этому же алгоритму
P.S. Алгоритм примерный, могут быть ошибки на плюс-минус один по позиции и не упомянуты проверки на конец массива.