Объединение двух возрастающих массивов в единый упорядоченный массив

Условие

Даны два массива целых чисел, каждый из которых отсортирован по возрастанию. Нужно реализовать функцию, которая создаёт и возвращает новый массив, содержащий все элементы из обоих исходных массивов, упорядоченные также по возрастанию.

Ответ

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

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

Время O(n+m), память нового массива O(n+m). Входы должны быть ненулевыми и уже отсортированными; пустые массивы поддерживаются. Дополнительная сортировка и TreeSet не нужны: последний ещё и удалил бы дубликаты.