Dúvida em recursividade

Boa tarde, Luidi! Tudo bem?

Analisando o seu documento, você está usando uma maneira um pouco diferente, mas interessante para entender a lógica da recursividade.

No passo 9, após as chamadas recursivas mergeSort(A, p, q) e mergeSort(A, q + 1, r), você deve chamar a função merge(A, p, q, r), já que não entra na condição de ser menor. Essa função é responsável por mesclar as duas metades ordenadas do array A e garantir que o array seja ordenado corretamente.

Portanto, o passo 9 seria a chamada da função merge(A, p, q, r).

Espero ter ajudado. Continue estudando e praticando para aprimorar ainda mais seus conhecimentos e em caso de dúvidas recorra ao fórum.

Grande abraço e bons estudos!

Estava revendo esse passo a passo que informei e estava errada em relação ao algoritmo que estava analisando. Coloquei alguns System.out.println() com informações relevantes em algumas partes do código para acompanhar o seu desenvolvimento passo a passo. Com isso refiz o passo a passo utilizando outro lógica, com base nas informações que obtive. Tenho uma dúvida: Tem alguma fórmula para determinar o número de trocas ocorridas em um array decrescente com 6 elementos? Ex: quantas trocas ocorrem para ordenar esse array decrescente: A[5,4,3,2,1,0]? No meu código deu 16 trocas, porém quando faço a mão dá 9 trocas.

Código:

public static  void mergeSort(int[] A, int p, int r) {
        
        if (p < r) {
            int q = (p + r) / 2; // Em Java, a divisão de inteiros já arredonda para baixo
            System.out.println("+Passo" +cont + "\nP = " +p + "\nQ = " +q + "\nR = " +r +"\nMerge-Sort1(A, " +p +", " +q +")");
            cont++;
            mergeSort(A, p, q);
            System.out.println("-Passo" +cont + "\nP = " +p + "\nQ = " +q + "\nR = " +r +"\nMerge-Sort2(A, " +(q+1) +", " +r +")");
            cont++;
            mergeSort(A, q + 1, r);
            System.out.println(";Passo" +cont + "\nP = " +p + "\nQ = " +q + "\nR = " +r +"\nMerge(A, " +p + ", " +q + ", " +r + ")");
            cont++;
            merge(A, p, q, r);
        }
    }
    
    public static void merge(int[] A, int p, int q, int r) {
        System.out.println("Passo 1 - Merge(A, " +p + ", " +q + ", " +r + ")");
        int n1 = q - p + 1;
        int n2 = r - q;
        System.out.println("P = " + p);
        System.out.println("Q = " + q);
        System.out.println("R = " + r);
        System.out.println("N1 = " + n1);
        System.out.println("N2 = " + n2);
        // Criando arrays temporários
        System.out.println("Passo 2 - Merge(A, " +p + ", " +q + ", " +r + ")");
        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = A[p + i];
            System.out.println("L["+i+"] = " +L[i]);}
        
        System.out.println("Passo 3 - Merge(A, " +p + ", " +q + ", " +r + ")");
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + 1 + j];
            System.out.println("R["+j+"] = " +R[j]);}
        
        System.out.println("Passo 4 - Merge(A, " +p + ", " +q + ", " +r + ")");
        int i = 0, j = 0, k = p;
        System.out.println("i = " +i + "\nj = " +j + "\nk = " +k);

        System.out.println("Passo 5 - Merge(A, " +p + ", " +q + ", " +r + ")");
        mostrarArray(A);
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                System.out.println(A[k] + " Troca com " +R[j]);
                System.out.println("A = [" +A[k] + "(idx " + k + ")" + ", " +R[j] + "]");
                A[k] = R[j];
                System.out.println("A = [" +A[k] + "(idx " + k + ")" + ", " +R[j] + "]");
                mostrarArray(A);
                j++;
              
            }
            k++;
            numeroTrocas++;
        }
        
        System.out.println("Passo 6 - Merge(A, " +p + ", " +q + ", " +r + ")");
        System.out.println("i = " +i + "\nj = " +j + "\nk = " +k);
        mostrarArray(A);
        while (i < n1) {
            System.out.println(A[k] + " Troca com " +L[i]);
            System.out.println("A = [" +A[k] + "(idx " + k + ") " + ", " +L[i] + "]");
            A[k] = L[i];
            System.out.println("A = [" +A[k] + "(idx " + k + ") " + ", " +L[i] + "]");
            mostrarArray(A);
            i++;
            k++;
            numeroTrocas++;
        }

        System.out.println("Passo 7 - Merge(A, " +p + ", " +q + ", " +r + ")");
        while (j < n2) {
            A[k] = R[j];
            j++;
            k++;
            numeroTrocas++;
        }
    }

Trocas feitas a mão:

https://drive.google.com/file/d/1AtmyymyQp2q3aaPyG3cvjGtZSGlA73s0/view?usp=sharing 

Passo a passo do Merge-Sort:

https://drive.google.com/drive/folders/1VHeDUj5EM_ImQMxgkSbH8_So4iA7hTkV?usp=drive_link 

Passo a passo de todos os Merge:

https://drive.google.com/drive/folders/1Y1L345mJ308bdA0YfunV3a1o06Ne1W1e?usp=drive_link