Questions about Recursion in the MergeSort function [C]

Question

Questions about Recursion in the MergeSort function [C]

Navigation

#1 by (3 votes)

3

I have a question about recursion. In fact, I'm not understanding the workings. 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 call of the recursive function MergeSort . Even when it gets 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 would it stop calling the function MergeSort (V, inicio , meio) and call the function MergeSort (V, meio+1, fim) ?

c

asked by anonymous 17.11.2015 / 11:40

1 answer

Use-case diagram - include and extend PHPMailler Error sending SMTP email connect () failed. UOL HOST

score 3 · Accepted Answer

I think the best way to explain this is for 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

V[5] 0 enters the function and calculates meio = 3 . It calls the first MergeSort. (left side).

V[3] 1 enters the function and calculates meio = 2 . It calls the first MergeSort.

V[2] 2 enters the function and calculates meio = 1 . It calls the first MergeSort.

V[1] 3 enters the function and does nothing because of if .

Returns to 3. by calling second MergeSort function.

V[1] 3 enters the function and does nothing because of if .

Returns to 3. by calling merge .

Returns to 2. by calling second MergeSort function.

V[1] 4 enters the function and does nothing because of if .

Returns to 2. by calling merge .

Returns to 1. by calling the second MergeSort function. (right side).

...

Returns to 1. by calling merge .

Return from V ordered.