Questions about Recursion in the Mergesort function [C]

Question

I have a question about recursiveness. Actually, I’m not understanding how it works. Come on! I have the following function:

void MergeSort (int *V, int inicio, int fim) {
    int meio;
    if (inicio < fim) {
        meio = floor ((inicio + fim) /2);
        MergeSort (V, inicio, meio);
        MergeSort (V, meio+1, fim);
        merge (V, inicio, meio, fim);
    }
}

My question is the recursive function call MergeSort. Even when he keeps calling the first function MergeSort(V, inicio, meio) and when it stops and starts calling the second function MergeSort( v, meio +1, fim). I understand the following.

void MergeSort (int *V, int inicio, int fim) {
    int meio;                                                                          

    if (inicio < fim) {
        meio = floor ((inicio + fim) /2);
        MergeSort (V, inicio, meio); // chama novamente essa funcao. Pare a função que esta sendo executada

        int meio;
        if (inicio < fim) {
            meio = floor ((inicio+meio)/2)
            mergesort (V, inicio, meio) //chama novamente essa funcao. Pare a função que esta sendo executada
        }
    }
}

At what point in the program it would stop calling the function MergeSort (V, inicio , meio) and call the function MergeSort (V, meio+1, fim) ?

Answer 1

I think the best way to explain this is by a graph:

Mergesort

void MergeSort (int *V, int inicio, int fim) {
    if (inicio < fim){
        int meio;
        meio = floor ((inicio + fim) /2);
        MergeSort (V, inicio, meio); // {1}
        MergeSort (V, meio+1, fim);  // {2}
        merge (V, inicio, meio, fim);
    }
}

Explanation

1. V[5] 0 enters the function and calculates meio = 3. Calls the first Mergesort. (left side).
2. V[3] 1 enters the function and calculates meio = 2. Call the first Mergesort.
3. V[2] 2 enters the function and calculates meio = 1. Call the first Mergesort.
4. V[1] 3 enters the function and does nothing because of the if.
5. Resumption of the 3. calling second Mergesort function.
6. V[1] 3 enters the function and does nothing because of the if.
7. Resumption of the 3. calling the merge.
8. Resumption of the 2. calling second Mergesort function.
9. V[1] 4 enters the function and does nothing because of the if.
10. Resumption of the 2. calling the merge.
11. Resumption of the 1. calling second Mergesort function. (right side).
12. ...
13. ...
14. ...
15. Resumption of the 1. calling the merge.
16. Return of V ordained.