¿Cómo fusionar dos matrices ordenadas en una matriz ordenada? [cerrado]

Esto me lo pidieron en una entrevista y esta es la solución que proporcioné:

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 una forma más eficiente de hacer esto?

Editar: métodos de longitud corregidos.

May 11 '11 08:05 Behrooz Karjoo

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;
}

¡Es un poco más compacto pero exactamente igual!

Jan 20 '2012 23:01 Mike Saull

Me sorprende que nadie haya mencionado esta implementación mucho más interesante, eficiente y 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;
}

Puntos de interés

Observe que realiza la misma cantidad o menos de operaciones que cualquier otro algoritmo O(n) , ¡pero literalmente en una sola declaración en un solo bucle while!
Si dos matrices son aproximadamente del mismo tamaño, entonces la constante para O(n) es la misma. Sin embargo, si las matrices están realmente desequilibradas, las versiones con System.arraycopyganarían porque internamente pueden hacer esto con una sola instrucción de ensamblaje x86.
Aviso a[i] >= b[j]en lugar de a[i] > b[j]. Esto garantiza la "estabilidad" que se define como cuando los elementos de a y b son iguales, queremos elementos de a antes que b.

Jul 09 '2015 07:07 Shital Shah

Una mejora menor, pero después del bucle principal, puedes usar System.arraycopypara copiar la cola de cualquiera de las matrices de entrada cuando llegues al final de la otra. Sin embargo, eso no cambiará las O(n)características de rendimiento de su solución.

May 11 '2011 01:05 Greg Hewgill