(Solução) Implementação um pouco diferente

Considerando que nem sempre temos um array que é a união de dois arrays ordenados, fiz essa implementação que considera dois arrays não ordenados e faz as manipulações para ordenar e realizar o merge em uma lista (o tipo de saída como lista é apenas para fins de praticidade, para não precisar implementar um for para printar cada item da lista depois).

private static String[] uneArrays(String[] array1, String[] array2) {        
    String[] uniaoArrays = new String[array1.length + array2.length];
    int posicaoLivre = 0;

    Arrays.sort(array1);
    Arrays.sort(array2);

    for(int i = 0; i < array1.length; i++) {
        uniaoArrays[posicaoLivre] = array1[i];
        posicaoLivre++;
    }
    for(int i = 0; i < array2.length;i++) {
        uniaoArrays[posicaoLivre] = array2[i];
        posicaoLivre++;
    }

    return uniaoArrays;
}

public static List<String> intercalaStrings(String[] array1, String[] array2) {
    String[] uniaoArrays = uneArrays(array1, array2);
    String[] resultado = new String[uniaoArrays.length];

    int ponteiroArray1 = 0;
    int ponteiroArray2 = array1.length;
    int ponteiroResultado = 0;

    while(ponteiroArray1 < array1.length && ponteiroResultado < resultado.length) {
        if (uniaoArrays[ponteiroArray1].compareTo(uniaoArrays[ponteiroArray2]) <= 0) {
            resultado[ponteiroResultado]  = uniaoArrays[ponteiroArray1];
            ponteiroArray1++;
            ponteiroResultado++;
        } else if (uniaoArrays[ponteiroArray1].compareTo(uniaoArrays[ponteiroArray2]) > 0) {
            resultado[ponteiroResultado]  = uniaoArrays[ponteiroArray2];
            ponteiroArray2++;
            ponteiroResultado++;
        }
    } 

    while(ponteiroResultado < resultado.length) {
        resultado[ponteiroResultado] = uniaoArrays[ponteiroArray2];
        ponteiroArray2++;
        ponteiroResultado++;
    }

    return Arrays.asList(resultado);
}