I want to Know how its work

Question

I want to know what's happened after this function call itself is it will resume or it will keeping calling itself until condition became false

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

Welcome to SO. For such tiny programs you should start using a debugger. It will help you walk through the code and see what happens. You might also execute the instructions with pen&paper. — Gerhardh, Aug 07 '18 at 10:20
read up on [how recursion works in C](https://stackoverflow.com/questions/5631447/how-recursion-works-in-c) — Sander De Dycker, Aug 07 '18 at 10:52
I don't quite understand what you're asking, but it seems you might be looking for a basic explanation of recursion (which you can probably find plenty of online). — Bernhard Barker, Aug 07 '18 at 10:53
@Gerhardh Someone who doesn't understand recursion will probably have a hard time debugging a recursive function, or even just debugging period. — Bernhard Barker, Aug 07 '18 at 11:02
@Dukeling This is precisely the situation where a session in a debugger might tell you more than a thousand words. Stepping over the same code again and again and maybe looking at a call stack might open your eyes for recursion. Maybe the p&p version is a bit too hard, I agree. — Gerhardh, Aug 07 '18 at 12:19

Support Ukraine · Accepted Answer · 2018-08-07T11:47:55.830

it will keeping calling itself until condition became false

yes, that is how it works.

The algorithm takes a range l to r and split it into two ranges and calls mergesort on each of the ranges.

Example (to keep it short I use ms instead of mergeSort)

Initial series of calls:

ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)

Since the values 0 and 0 fails the condition l < r so that call will just return and the second call of mergeSort in previous recursion level will be executed. Leading to:

ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
                                                                |
                                                                --> ms(a, 1, 1)

Once again the values 1 and 1 fails the condition l < r so that call will just return and after the merge we will return to the previous recursion level and do the second call to mergeSort at that level.

ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
                                               |                |
                                               |                --> ms(a, 1, 1) 
                                               | 
                                               --> ms(a, 2, 2)

2 and 2 just makes us return to the previous recursion level where mergeSort is called the second time. I guess you see the picture now...

ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
             |                |                |                |
             |                |                |                --> ms(a, 1, 1) 
             |                |                | 
             |                |                --> ms(a, 2, 2)
             |                |
             |                --> ms(a, 3, 4) ---> ms(a, 3, 3)
             |                                 |
             |                                 --> ms(a, 4, 4)
             |
             --> ms(a, 5, 8) ---> ... finish this your self ...

Another approach for understanding the call sequence is to add a "recursion level" and do some simple print when mergeSort is called:

#include <stdio.h>

void mergeSort(int arr[], int l, int r, int level)
{
  printf("Recursion level %d l=%d r=%d\n", level, l, r);
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;

        // Sort first and second halves
        mergeSort(arr, l, m, level+1);
        mergeSort(arr, m+1, r, level+1);

        // merge commented out as it is irrelevant for the call sequence
        // merge(arr, l, m, r);
    }
}

int main()
{
  int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
  mergeSort(a, 0, 8, 0);
  return 0;
}

Output:

Recursion level 0 l=0 r=8
Recursion level 1 l=0 r=4
Recursion level 2 l=0 r=2
Recursion level 3 l=0 r=1
Recursion level 4 l=0 r=0
Recursion level 4 l=1 r=1
Recursion level 3 l=2 r=2
Recursion level 2 l=3 r=4
Recursion level 3 l=3 r=3
Recursion level 3 l=4 r=4
Recursion level 1 l=5 r=8
Recursion level 2 l=5 r=6
Recursion level 3 l=5 r=5
Recursion level 3 l=6 r=6
Recursion level 2 l=7 r=8
Recursion level 3 l=7 r=7
Recursion level 3 l=8 r=8

Same output but with level dependent indentation:

Recursion level 0 l=0 r=8
  Recursion level 1 l=0 r=4
    Recursion level 2 l=0 r=2
      Recursion level 3 l=0 r=1
        Recursion level 4 l=0 r=0
        Recursion level 4 l=1 r=1
      Recursion level 3 l=2 r=2
    Recursion level 2 l=3 r=4
      Recursion level 3 l=3 r=3
      Recursion level 3 l=4 r=4
  Recursion level 1 l=5 r=8
    Recursion level 2 l=5 r=6
      Recursion level 3 l=5 r=5
      Recursion level 3 l=6 r=6
    Recursion level 2 l=7 r=8
      Recursion level 3 l=7 r=7
      Recursion level 3 l=8 r=8

I want to Know how its work

1 Answers1