Como mesclar duas matrizes classificadas em uma matriz classificada? [fechadas]

Isso foi solicitado a mim em uma entrevista e esta é a solução que forneci:

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;
}

Existe uma maneira mais eficiente de fazer isso?

Editar: métodos de comprimento corrigidos.

Uma pequena melhoria, mas após o loop principal, você pode System.arraycopycopiar a cauda de qualquer matriz de entrada quando chegar ao final da outra. Isso não altera as O(n)características de desempenho da sua solução.

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)  
       answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

    while (i < a.length)  
        answer[k++] = a[i++];

    while (j < b.length)    
        answer[k++] = b[j++];

    return answer;
}

É um pouco mais compacto, mas exatamente o mesmo!

Estou surpreso que ninguém tenha mencionado essa implementação muito mais interessante, eficiente e compacta:

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;
}

Pontos de interesse

1. Observe que ele realiza o mesmo ou menos número de operações que qualquer outro O (n) algoritmo , mas literalmente em uma única instrução em um único loop while!
2. Se duas matrizes são aproximadamente do mesmo tamanho, a constante para O (n) é a mesma. Entretanto, se os arrays estiverem realmente desequilibrados, as versões comSystem.arraycopy vencerão, porque internamente isso pode ser feito com uma única instrução de montagem x86.
3. Observe em a[i] >= b[j]vez de a[i] > b[j]. Isso garante "estabilidade", definida como quando os elementos de aeb são iguais, queremos elementos de a antes de b.

Quaisquer melhorias que poderiam ser feitas seriam micro-otimizações, o algoritmo geral está correto.

Essa solução também é muito semelhante a outras postagens, exceto pelo uso de System.arrayCopy para copiar os elementos restantes da matriz.

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length +b.length];
    int i =0; int j = 0;int k = 0;
    while(i<a.length && j <b.length) {
        if(a[i]<b[j]) {
            result[k++] = a[i];
            i++;
        } else {
            result[k++] = b[j];
            j++;
        }
    }
    System.arraycopy(a, i, result, k, (a.length -i));
    System.arraycopy(b, j, result, k, (b.length -j));
    return result;
}

Aqui está a função atualizada. Ele remove duplicatas, espero que alguém ache isso útil:

public static long[] merge2SortedAndRemoveDublicates(long[] a, long[] b) {
    long[] answer = new long[a.length + b.length];
    int i = 0, j = 0, k = 0;
    long tmp;
    while (i < a.length && j < b.length) {
        tmp = a[i] < b[j] ? a[i++] : b[j++];
        for ( ; i < a.length && a[i] == tmp; i++);
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    while (i < a.length) {
        tmp = a[i++];
        for ( ; i < a.length && a[i] == tmp; i++);
        answer[k++] = tmp;
    }
    while (j < b.length) {
        tmp = b[j++];
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    return Arrays.copyOf(answer, k);
}

Isso pode ser feito em 4 instruções, como abaixo

 int a[] = {10, 20, 30};
 int b[]= {9, 14, 11};
 int res[]=new int[a.legth+b.length]; 
 System.arraycopy(a,0, res, 0, a.length); 
 System.arraycopy(b,0,res,a.length, b.length);
 Array.sort(res)

Eu tive que escrever em javascript, aqui está:

function merge(a, b) {
    var result = [];
    var ai = 0;
    var bi = 0;
    while (true) {
        if ( ai < a.length && bi < b.length) {
            if (a[ai] < b[bi]) {
                result.push(a[ai]);
                ai++;
            } else if (a[ai] > b[bi]) {
                result.push(b[bi]);
                bi++;
            } else {
                result.push(a[ai]);
                result.push(b[bi]);
                ai++;
                bi++;
            }
        } else if (ai < a.length) {
            result.push.apply(result, a.slice(ai, a.length));
            break;
        } else if (bi < b.length) {
            result.push.apply(result, b.slice(bi, b.length));
            break;
        } else {
            break;
        }
    }
    return result;
}

As coleções do Apache suportam o método collate desde a versão 4; você pode fazer isso usando o collatemétodo em:

org.apache.commons.collections4.CollectionUtils

Aqui citação de javadoc:

collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)

Mescla duas coleções classificadas ae b, em uma única lista classificada, de modo que a ordem dos elementos de acordo com o comparador c seja mantida.

Não reinvente a roda! Referência do documento: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

Integração do GallopSearch: O (log (n) * log (i)) vez de O (n)

Fui em frente e implementei a sugestão de barba cinzenta nos comentários. Principalmente porque eu precisava de uma versão de missão crítica altamente eficiente desse código.

• O código usa um gallopSearch que é O (log (i)) em que i é a distância do índice atual em que o índice relevante existe.
• O código usa um binarySearch para após a pesquisa de galope identificar o intervalo apropriado. Como o galope limitou isso a um intervalo menor, o binarySearch resultante também é O (log (i))
• O galope e a mesclagem são executados para trás. Isso não parece crítico à missão, mas permite a fusão de matrizes. Se uma de suas matrizes tiver espaço suficiente para armazenar os valores dos resultados, você pode simplesmente usá-la como a matriz mesclada e a matriz de resultados. Você deve especificar o intervalo válido dentro da matriz nesse caso.
• Não requer alocação de memória nesse caso (grandes economias em operações críticas). Ele simplesmente garante que não substitua e não possa sobrescrever nenhum valor não processado (o que só pode ser feito ao contrário). De fato, você usa a mesma matriz para as entradas e os resultados. Não sofrerá efeitos negativos.
• Eu sempre usei Integer.compare () para que isso pudesse ser alterado para outros fins.
• Há alguma chance de eu ter enganado um pouco e não utilizado informações que eu já havia provado anteriormente. Como pesquisa binária em um intervalo de dois valores, para os quais um valor já foi verificado. Também pode haver uma maneira melhor de indicar o loop principal, o valor de inversão de c não seria necessário se eles fossem combinados em duas operações em sequência. Desde que você saiba que fará um e outro sempre. Há espaço para um pouco de polimento.

Essa deve ser a maneira mais eficiente de fazer isso, com complexidade de tempo de O (log (n) * log (i)) vez de O (n). E, no pior dos casos, complexidade do tempo de O (n). Se suas matrizes forem desajeitadas e tiverem longas cadeias de valores juntas, isso diminuirá qualquer outra maneira de fazê-lo; caso contrário, será apenas melhor que elas.

Ele possui dois valores de leitura nas extremidades da matriz mesclada e o valor de gravação na matriz de resultados. Depois de descobrir qual é o valor final menor, ele faz uma busca galopante nessa matriz. 1, 2, 4, 8, 16, 32, etc. Quando encontra o intervalo em que o valor de leitura da outra matriz é maior. Ele pesquisa binário nesse intervalo (corta o intervalo pela metade, pesquisa pela metade correta, repita até o valor único). Em seguida, o array copia esses valores na posição de gravação. Lembre-se de que a cópia é movida por necessidade, de modo que não possa sobrescrever os mesmos valores da matriz de leitura (o que significa que a matriz de gravação e a matriz de leitura podem ser as mesmas). Em seguida, ele executa a mesma operação para a outra matriz, que agora é conhecida como menor que o novo valor de leitura da outra matriz.

static public int gallopSearch(int current, int[] array, int v) {
    int d = 1;
    int seek = current - d;
    int prevIteration = seek;
    while (seek > 0) {
        if (Integer.compare(array[seek], v) <= 0) {
            break;
        }
        prevIteration = seek;
        d <<= 1;
        seek = current - d;
        if (seek < 0) {
            seek = 0;
        }
    }
    if (prevIteration != seek) {
        seek = binarySearch(array, seek, prevIteration, v);
        seek = seek >= 0 ? seek : ~seek;
    }
    return seek;
}

static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = list[mid];
        int cmp = Integer.compare(midVal, v);
        if (cmp < 0) {
            low = mid + 1;
        } else if (cmp > 0) {
            high = mid - 1;
        } else {
            return mid;// key found
        }
    }
    return -(low + 1);// key not found.
}

static public int[] sortedArrayMerge(int[] a, int[] b) {
    return sortedArrayMerge(null, a, a.length, b, b.length);
}

static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) {
    int write = aRead + bRead, length, gallopPos;
    if ((results == null) || (results.length < write)) {
        results = new int[write];
    }
    if (aRead > 0 && bRead > 0) {
        int c = Integer.compare(a[aRead - 1], b[bRead - 1]);
        while (aRead > 0 && bRead > 0) {
            switch (c) {
                default:
                    gallopPos = gallopSearch(aRead, a, b[bRead-1]);
                    length = (aRead - gallopPos);
                    write -= length;
                    aRead = gallopPos;
                    System.arraycopy(a, gallopPos--, results, write, length);
                    c = -1;
                    break;
                case -1:
                    gallopPos = gallopSearch(bRead, b, a[aRead-1]);
                    length = (bRead - gallopPos);
                    write -= length;
                    bRead = gallopPos;
                    System.arraycopy(b, gallopPos--, results, write, length);
                    c = 1;
                    break;
            }
        }
    }
    if (bRead > 0) {
        if (b != results) {
            System.arraycopy(b, 0, results, 0, bRead);
        }
    } else if (aRead > 0) {
        if (a != results) {
            System.arraycopy(a, 0, results, 0, aRead);
        }
    }
    return results;
}

Essa deve ser a maneira mais eficiente de fazer isso.

Algumas respostas tiveram uma capacidade de remoção duplicada. Isso exigirá um algoritmo O (n) porque você deve realmente comparar cada item. Então, aqui está um exemplo independente, a ser aplicado após o fato. Você não pode galopar várias entradas até o fim, se precisar olhar para todas elas, embora possa galopar pelas duplicatas, se tiver muitas delas.

static public int removeDuplicates(int[] list, int size) {
    int write = 1;
    for (int read = 1; read < size; read++) {
        if (list[read] == list[read - 1]) {
            continue;
        }
        list[write++] = list[read];
    }
    return write;
}

Atualização: resposta anterior, código não horrível, mas claramente inferior ao acima.

Outra hiper otimização desnecessária. Ele não apenas chama arraycopy para os bits finais, mas também para o começo. Processando qualquer não sobreposição introdutória em O (log (n)) por um binarySearch nos dados. O (log (n) + n) é O (n) e, em alguns casos, o efeito será bastante pronunciado, especialmente em situações em que não há sobreposição entre as matrizes mescladas.

private static int binarySearch(int[] array, int low, int high, int v) {
    high = high - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = array[mid];
        if (midVal > v)
            low = mid + 1;
        else if (midVal < v)
            high = mid - 1;
        else
            return mid; // key found
    }
    return low;//traditionally, -(low + 1);  // key not found.
}

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length + b.length];
    int k, i = 0, j = 0;
    if (a[0] > b[0]) {
        k = i = binarySearch(b, 0, b.length, a[0]);
        System.arraycopy(b, 0, result, 0, i);
    } else {
        k = j = binarySearch(a, 0, a.length, b[0]);
        System.arraycopy(a, 0, result, 0, j);
    }
    while (i < a.length && j < b.length) {
        result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
    }
    if (j < b.length) {
        System.arraycopy(b, j, result, k, (b.length - j));
    } else {
        System.arraycopy(a, i, result, k, (a.length - i));
    }
    return result;
}

Aqui está um formulário abreviado escrito em javascript:

function sort( a1, a2 ) {

    var i = 0
        , j = 0
        , l1 = a1.length
        , l2 = a2.length
        , a = [];

    while( i < l1 && j < l2 ) {

        a1[i] < a2[j] ? (a.push(a1[i]), i++) : (a.push( a2[j]), j++);
    }

    i < l1 && ( a = a.concat( a1.splice(i) ));
    j < l2 && ( a = a.concat( a2.splice(j) ));

    return a;
}

    public class Merge {

    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }

        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);
    }


   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }


   /***********************************************************************
    *  Index mergesort
    ***********************************************************************/
    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = index[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                    index[k] = aux[j++];
            else if (j > hi)                     index[k] = aux[i++];
            else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
            else                                 index[k] = aux[i++];
        }
    }

    // return a permutation that gives the elements in a[] in ascending order
    // do not change the original array a[]
    public static int[] indexSort(Comparable[] a) {
        int N = a.length;
        int[] index = new int[N];
        for (int i = 0; i < N; i++)
            index[i] = i;

        int[] aux = new int[N];
        sort(a, index, aux, 0, N-1);
        return index;
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, index, aux, lo, mid);
        sort(a, index, aux, mid + 1, hi);
        merge(a, index, aux, lo, mid, hi);
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    // Read strings from standard input, sort them, and print.
    public static void main(String[] args) {
        String[] a = StdIn.readStrings();
        Merge.sort(a);
        show(a);
    }
}

Acho que a introdução da lista de pulos para uma matriz classificada maior pode reduzir o número de comparações e acelerar o processo de cópia na terceira matriz. Isso pode ser bom se a matriz for muito grande.

public int[] merge(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int aIndex, bIndex = 0;

    for (int i = 0; i < result.length; i++) {
        if (aIndex < a.length && bIndex < b.length) {
            if (a[aIndex] < b[bIndex]) {
                result[i] = a[aIndex];
                aIndex++;
            } else {
                result[i] = b[bIndex];
                bIndex++;
            }
        } else if (aIndex < a.length) {
            result[i] = a[aIndex];
            aIndex++;
        } else {
            result[i] = b[bIndex];
            bIndex++;
        }
    }

    return result;
}

public static int[] merge(int[] a, int[] b) {
    int[] mergedArray = new int[(a.length + b.length)];
    int i = 0, j = 0;
    int mergedArrayIndex = 0;
    for (; i < a.length || j < b.length;) {
        if (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                mergedArray[mergedArrayIndex] = a[i];
                i++;
            } else {
                mergedArray[mergedArrayIndex] = b[j];
                j++;
            }
        } else if (i < a.length) {
            mergedArray[mergedArrayIndex] = a[i];
            i++;
        } else if (j < b.length) {
            mergedArray[mergedArrayIndex] = b[j];
            j++;
        }
        mergedArrayIndex++;
    }
    return mergedArray;
}

O algoritmo pode ser aprimorado de várias maneiras. Por exemplo, é razoável verificar, se a[m-1]<b[0]oub[n-1]<a[0] . Em qualquer um desses casos, não há necessidade de fazer mais comparações. O algoritmo pode apenas copiar as matrizes de origem na resultante na ordem correta.

Aprimoramentos mais complicados podem incluir a pesquisa de peças intercaladas e executar o algoritmo de mesclagem apenas para elas. Isso pode economizar muito tempo, quando os tamanhos das matrizes mescladas diferem em dezenas de vezes.

Esse problema está relacionado ao algoritmo mergesort, no qual duas sub-matrizes classificadas são combinadas em uma única sub-matriz classificada. O CLRS livro do fornece um exemplo do algoritmo e limpa a necessidade de verificar se o fim foi alcançado adicionando um valor sentinela (algo que se compara e "maior que qualquer outro valor") ao final de cada matriz.

Eu escrevi isso em Python, mas deve ser traduzido também para Java:

def func(a, b):
    class sentinel(object):
        def __lt__(*_):
            return False

    ax, bx, c = a[:] + [sentinel()], b[:] + [sentinel()], []
    i, j = 0, 0

    for k in range(len(a) + len(b)):
        if ax[i] < bx[j]:
            c.append(ax[i])
            i += 1
        else:
            c.append(bx[j])
            j += 1

    return c

Você pode usar 2 threads para preencher a matriz resultante, uma de frente e outra de trás.

Isso pode funcionar sem qualquer sincronização no caso de números, por exemplo, se cada thread inserir metade dos valores.

//How to merge two sorted arrays into a sorted array without duplicates?
//simple C Coding
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

main()
{
    int InputArray1[] ={1,4,5,7,8,9,12,13,14,17,40};
    int InputArray2[] ={4,5,11,14,15,17,18,19,112,122,122,122,122};
    int n=10;
    int OutputArray[30];
    int i=0,j=0,k=0;
    //k=OutputArray
    while(i<11 && j<13)
    {
        if(InputArray1[i]<InputArray2[j])
        {
            if (k == 0 || InputArray1[i]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray1[i];
            }
            i=i+1;
        }
        else if(InputArray1[i]>InputArray2[j])
        {
            if (k == 0 || InputArray2[j]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray2[j];
            }
            j=j+1;
        }
        else
        {
            if (k == 0 || InputArray1[i]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray1[i];
            }
            i=i+1;
            j=j+1;
        }
    };
    while(i<11)
    {
        if(InputArray1[i]!= OutputArray[k-1])
            OutputArray[k++] = InputArray1[i++];
        else
            i++;
    }
    while(j<13)
    {
        if(InputArray2[j]!= OutputArray[k-1])
            OutputArray[k++] = InputArray2[j++];
        else
            j++;
    }
    for(i=0; i<k; i++)
    {
        printf("sorted data:%d\n",OutputArray[i]);
    };
}

public static int[] merge(int[] listA, int[] listB) {
        int[] mergedList = new int[ listA.length + listB.length];
        int i = 0; // Counter for listA
        int j = 0; // Counter for listB
        int k = 0; // Counter for mergedList
        while (true) {
            if (i >= listA.length && j >= listB.length) {
                break;
            }
            if (i < listA.length && j < listB.length) { // If both counters are valid.
                if (listA[i] <= listB[j]) {
                    mergedList[k] = listA[i];
                    k++;
                    i++;
                } else {
                    mergedList[k] = listB[j];
                    k++;
                    j++;
                }
            } else if (i < listA.length && j >= listB.length) { // If only A's counter is valid.
                mergedList[k] = listA[i];
                k++;
                i++;
            } else if (i <= listA.length && j < listB.length) { // If only B's counter is valid
                mergedList[k] = listB[j];
                k++;
                j++;
            }
        }
        return mergedList;
    }

var arrCombo = function(arr1, arr2){
  return arr1.concat(arr2).sort(function(x, y) {
    return x - y;
  });
};

Minha linguagem de programação favorita é JavaScript

function mergeSortedArrays(a, b){
    var result = [];

    var sI = 0;
    var lI = 0;
    var smallArr;
    var largeArr;
    var temp;

    if(typeof b[0] === 'undefined' || a[0]<b[0]){
        smallArr = a;
        largeArr = b;
    } else{
        smallArr = b;
        largeArr = a;
    }

    while(typeof smallArr[sI] !== 'undefined'){
        result.push(smallArr[sI]);
        sI++;

        if(smallArr[sI]>largeArr[lI] || typeof smallArr[sI] === 'undefined'){
            temp = smallArr;
            smallArr = largeArr;
            largeArr = temp;
            temp = sI;
            sI = lI;
            lI = temp;
        }
    }
    return result;
}

Talvez use System.arraycopy

public static byte[] merge(byte[] first, byte[] second){
    int len = first.length + second.length;
    byte[] full = new byte[len];
    System.arraycopy(first, 0, full, 0, first.length);
    System.arraycopy(second, 0, full, first.length, second.length);
    return full;
}

public static void main(String[] args) {
    int[] arr1 = {2,4,6,8,10,999};
    int[] arr2 = {1,3,5,9,100,1001};

    int[] arr3 = new int[arr1.length + arr2.length];

    int temp = 0;

    for (int i = 0; i < (arr3.length); i++) {
        if(temp == arr2.length){
            arr3[i] = arr1[i-temp];
        }
        else if (((i-temp)<(arr1.length)) && (arr1[i-temp] < arr2[temp])){
                arr3[i] = arr1[i-temp];
        }
        else{
            arr3[i] = arr2[temp];
            temp++;
        }
    }

    for (int i : arr3) {
        System.out.print(i + ", ");
    }
}

A saída é:

1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,

Você pode usar operadores ternários para tornar o código um pouco mais compacto

public static int[] mergeArrays(int[] a1, int[] a2) {
    int[] res = new int[a1.length + a2.length];
    int i = 0, j = 0;

    while (i < a1.length && j < a2.length) {
        res[i + j] = a1[i] < a2[j] ? a1[i++] : a2[j++];
    }

    while (i < a1.length) {
        res[i + j] = a1[i++];
    }

    while (j < a2.length) {
        res[i + j] = a2[j++];
    }

    return res;
}

public static int[] mergeSorted(int[] left, int[] right) {
    System.out.println("merging " + Arrays.toString(left) + " and " + Arrays.toString(right));
    int[] merged = new int[left.length + right.length];
    int nextIndexLeft = 0;
    int nextIndexRight = 0;
    for (int i = 0; i < merged.length; i++) {
        if (nextIndexLeft >= left.length) {
            System.arraycopy(right, nextIndexRight, merged, i, right.length - nextIndexRight);
            break;
        }
        if (nextIndexRight >= right.length) {
            System.arraycopy(left, nextIndexLeft, merged, i, left.length - nextIndexLeft);
            break;
        }
        if (left[nextIndexLeft] <= right[nextIndexRight]) {
            merged[i] = left[nextIndexLeft];
            nextIndexLeft++;
            continue;
        }
        if (left[nextIndexLeft] > right[nextIndexRight]) {
            merged[i] = right[nextIndexRight];
            nextIndexRight++;
            continue;
        }
    }
    System.out.println("merged : " + Arrays.toString(merged));
    return merged;
}

Apenas um pouco diferente da solução original

Para marcar duas matrizes ordenadas em complexidade de tempo O (m + n), use a abordagem abaixo apenas com um loop. m e n é o comprimento da primeira matriz e da segunda matriz.

public class MargeSortedArray {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,4,7};
        int[] array2 = new int[]{2,5,6,8,12,45};
        int[] newarry = margeToSortedArray(array, array2);
        //newarray is marged array
    }

    // marge two sorted array with o(a+n) time complexity
    public static int[] margeToSortedArray(int[] array, int[] array2) {
        int newarrlen = array.length+array2.length;
        int[] newarr = new int[newarrlen];

        int pos1=0,pos2=0;
        int len1=array.length, len2=array2.length;

        for(int i =0;i<newarrlen;i++) {     
            if(pos1>=len1) {
                newarr[i]=array2[pos2];
                pos2++;
                continue;
            }
            if(pos2>=len2) {
                newarr[i]=array[pos1];
                pos1++;
                continue;
            }

            if(array[pos1]>array2[pos2]) {
                newarr[i]=array2[pos2];
                pos2++;
            } else {
                newarr[i]=array[pos1];
                pos1++;
            }   
        }

        return newarr;
    }

}

var arr1 = [2,10,20,30,100];
var arr2 = [2,4,5,6,7,8,9];
var j = 0;
var i =0;
var newArray = [];

for(var x=0;x< (arr1.length + arr2.length);x++){
    if(arr1[i] >= arr2[j]){                //check if element arr2 is equal and less than arr1 element
        newArray.push(arr2[j]);
      j++;
    }else if(arr1[i] < arr2[j]){            //check if element arr1 index value  is less than arr2 element
        newArray.push(arr1[i]);
        i++;
    }
    else if(i == arr1.length || j < arr2.length){    // add remaining arr2 element
        newArray.push(arr2[j]);
        j++
    }else{                                                   // add remaining arr1 element
        newArray.push(arr1[i]); 
        i++
    }

}

console.log(newArray);

Como a pergunta não assume nenhum idioma específico. Aqui está a solução em Python. Supondo que as matrizes já estejam classificadas.

Abordagem 1 - usando matrizes numpy: import numpy

arr1 = numpy.asarray([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 11, 14, 15, 55])
arr2 = numpy.asarray([11, 32, 43, 45, 66, 76, 88])

array = numpy.concatenate((arr1,arr2), axis=0)
array.sort()

Abordagem 2 - Usando a lista, assumindo que as listas sejam classificadas.

list_new = list1.extend(list2)
list_new.sort()

Aqui está a minha implementação java que remove duplicado.

public static int[] mergesort(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    int i = 0, j = 0, k = 0, duplicateCount = 0;

    while (i < a.length || j < b.length) {
        if (i < a.length && j < b.length) {
            if (a[i] == b[j]) {
                c[k] = a[i];
                i++;j++;duplicateCount++;
            } else {
                c[k] = a[i] < b[j] ? a[i++] : b[j++];
            }
        } else if (i < a.length) {
            c[k] = a[i++];
        } else if (j < a.length) {
            c[k] = b[j++];
        }
        k++;
    }

    return Arrays.copyOf(c, c.length - duplicateCount);
}