Série Preparação para Entrevistas: #5 Entenda o Merge Sort

// Método principal para iniciar o processo de Merge Sort
private static void mergeSort(int[] array) {
    // Um array temporário é usado para auxiliar na fusão dos subarrays
    mergeSort(array, new int[array.length], 0, array.length - 1);
}

// Método auxiliar de Merge Sort que utiliza a abordagem de dividir para conquistar
private static void mergeSort(int[] array, int[] temp, int inicioEsquerda, int fimDireita) {
    // Condição de base: se o subarray tem um único elemento, não é necessário ordenar
    if (inicioEsquerda >= fimDireita) {
        return;
    }

    // Encontra o ponto médio para dividir o array em subarrays
    int meio = (inicioEsquerda + fimDireita) / 2;
    // Ordena recursivamente a metade esquerda do array
    mergeSort(array, temp, inicioEsquerda, meio);
    // Ordena recursivamente a metade direita do array
    mergeSort(array, temp, meio + 1, fimDireita);
    // Funde as duas metades ordenadas
    merge(array, temp, inicioEsquerda, fimDireita);
}

// Funde duas metades ordenadas de um array em um único subarray ordenado
private static void merge(int[] array, int[] temp, int inicioEsquerda, int fimDireita) {
    // Calcula o fim do subarray esquerdo e o início do subarray direito
    int fimEsquerda = (inicioEsquerda + fimDireita) / 2;
    int inicioDireita = fimEsquerda + 1;
    // Inicializa os ponteiros para acompanhar a posição atual em cada subarray e no array temporário
    int esquerdaAtual = inicioEsquerda;
    int direitaAtual = inicioDireita;
    int tempIndice = inicioEsquerda;

    // Enquanto houver elementos em ambos os subarrays, compara e ordena no array temporário
    while (esquerdaAtual <= fimEsquerda && direitaAtual <= fimDireita) {
        if (array[esquerdaAtual] < array[direitaAtual]) {
            temp[tempIndice++] = array[esquerdaAtual++];
        } else {
            temp[tempIndice++] = array[direitaAtual++];
        }
    }

    // Copia os elementos restantes do subarray esquerdo para o array temporário
    System.arraycopy(array, esquerdaAtual, temp, tempIndice, fimEsquerda - esquerdaAtual + 1);
    // Copia os elementos restantes do subarray direito para o array temporário
    System.arraycopy(array, direitaAtual, temp, tempIndice, fimDireita - direitaAtual + 1);
    // Copia os elementos do array temporário de volta para o array original
    System.arraycopy(temp, inicioEsquerda, array, inicioEsquerda, fimDireita - inicioEsquerda + 1);
}