Слияние двух упорядоченных массивов

Условие

Даны два массива, элементы которых уже отсортированы. Необходимо получить единый массив, в котором все элементы расположены в порядке возрастания (или неубывания). Ожидаемый итоговый массив: [1, 1, 2, 3, 4, 4]

int[] arrA = {1, 2, 4};
int[] arrB = {1, 3, 4};

Ответ

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

public int[] merge(int[] a, int[] b) {
    int[] result = new int[Math.addExact(a.length, b.length)];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length) {
        result[k++] = a[i] <= b[j] ? a[i++] : b[j++];
    }
    while (i < a.length) result[k++] = a[i++];
    while (j < b.length) result[k++] = b[j++];
    return result;
}

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