Eu estive fora de contato com Algoritmos por um tempo e comecei a revisar meus conceitos nos dias de hoje. Para minha surpresa, a última lembrança da minha habilidade de recursão foi que eu era boa nisso, mas não mais. Então, eu tenho uma pergunta básica para vocês que está me confundindo. Por favor, veja o código abaixo primeiro ..

private void mergesort(int low, int high) {
    if (low < high) {
        int middle = (low + high)/2 ;
        System.out .println ("Before the 1st Call");
        mergesort(low, middle);
        System.out .println ("After the 1st Call");
        mergesort(middle+1, high);
        System.out .println ("After the 2nd Call");
        merge(low, middle, high);
    }
}

A chamada de função

mergesort(0,7);

E a saída é

Antes da 1ª chamada

Antes da 1ª chamada

Antes da 1ª chamada

Após a 1ª chamada

Após a 2ª chamada

Após a 1ª chamada

Antes da 1ª chamada

Após a 1ª chamada

Após a 2ª chamada

Após a 2ª chamada

Após a 1ª chamada

Antes da 1ª chamada

Antes da 1ª chamada

Após a 1ª chamada

Após a 2ª chamada

Após a 1ª chamada

Antes da 1ª chamada

Após a 1ª chamada

Após a 2ª chamada

Após a 2ª chamada

Após a 2ª chamada

A coisa me confundindo no código acima e resultado é a segunda chamada recursiva. Estou entendendo o fluxo até a quarta linha de saída (ou seja: após a primeira chamada). Mas eu não consigo entender por que ele produz (após a 2 ª chamada) após (após a 1 ª chamada). De acordo com o que estou entendendo do código Após a saída (Após a 1ª Chamada) a função mergesort com o parâmetro (middle + 1, high) deve ser chamada e deve sair (Before the 1st call) e entrar na chamada recursiva com o mergesort (baixo, médio). Eu sou compatível com uma função de chamada recursiva e entendo e estou sincronizado com o exemplo de fibonacci de foreg.