Функция объединения двух упорядоченных массивов

Условие

Реализуйте функцию, принимающую два уже отсортированных массива целых чисел (например, arrA и arrB), объединяющую их элементы и возвращающую новый массив, в котором все числа расположены в порядке возрастания. При этом исходные массивы должны оставаться неизменными.

Ответ

Сливайте массивы двумя указателями: сравнивайте текущие элементы и переносите меньший в новый массив. Так сохраняются исходные данные и все дубликаты.

function mergeSorted(a, b) {
  const result = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    result.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }
  while (i < a.length) result.push(a[i++]);
  while (j < b.length) result.push(b[j++]);
  return result;
}

Для [1, 3, 3] и [2, 3] получится [1, 2, 3, 3, 3]. Оба входа предполагаются отсортированными по возрастанию. Время O(n + m), память результата O(n + m); повторная сортировка объединения не нужна.