Thread: Mergesort recursion Help in C

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    4

    Mergesort recursion Help in C

    Hello all, I am confused with the recursion in Mergersort., i came across this C code and while trying to understand the recursion involved ,i added several trace statements to know he states of the variables. I am confused on the values retained in variables in a recursive call.
    Code:
    The array values are arr[]={2,3,5}. I am posting the code that recursively splits the array
    
    
    Code:
    int mergesort(int a[], int low, int high)
    {
    int mid;
    printf("\nlow=%d high=%d\n",low,high);
    if(low<high)
    {
    mid=(low+high)/2;
    
    printf("\nbefore mid mid=%d high=%d,low=%d\n",mid,high,low);
    
    mergesort(a,low,mid);
    
    printf("\nbefore mid+1 mid=%d high=%d,low=%d\n",mid,high,low);
    
    mergesort(a,mid+1,high);
    
    printf("\nafter mid+1 mid=%d high=%d,low=%d\n",mid,high,low);
    
    printf("\ncalling merge");
    
    printf("\ncalling merge mid=%d high=%d,low=%d\n",mid,high,low);
    
    merge(a,low,high,mid);
    }
    return(0);
    }
    Now the output for this is:
    Code:
    low=0 high=2
    
    before mid mid=1 high=2,low=0
    
    low=0 high=1
    
    before mid mid=0 high=1,low=0
    
    low=0 high=0
    
    before mid+1 mid=0 high=1,low=0
    
    low=1 high=1
    
    after mid+1 mid=0 high=1,low=0
    
    calling merge
    calling merge mid=0 high=1,low=0
    
    before mid+1 mid=1 high=2,low=0
    
    low=2 high=2
    
    after mid+1 mid=1 high=2,low=0
    
    calling merge
    calling merge mid=1 high=2,low=0
    
    sorted array:
    2
    3
    5
    low=0 high=0
    before mid+1 mid=0 high=1,low=0
    :I dont understand how the value of high is 1 as after computing mid the value sent is mergesort(a,0,0) and thus low is 0 and high must be 0?

    calling merge
    calling merge mid=0 high=1,low=0
    before mid+1 mid=1 high=2,low=0:
    Here the merge function is passed with the following values merge(a,low,mid,high):merge(a,0,0,1) and after the function returns the next call to mergesort(a,mid+1,high) has the values of mid as 1,high as 2 and low as 0. I am stuck at the values of mid and high here??

    Any explanation would be helpful. I hope there is some clarity in my doubts. Thanks

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,541
    Write it as
    Code:
    int mergesort(int a[], int low, int high,int depth)
    {
    int mid;
    printf("\nlow=%d high=%d\n",low,high);
    if(low<high)
    {
    mid=(low+high)/2;
    
    printf("\n(%d) before mid mid=%d high=%d,low=%d\n",depth,mid,high,low);
    
    mergesort(a,low,mid,depth+1);
    
    printf("\n(%d) before mid+1 mid=%d high=%d,low=%d\n",depth,mid,high,low);
    
    mergesort(a,mid+1,high,depth+1);
    
    printf("\n(%d) after mid+1 mid=%d high=%d,low=%d\n",depth,mid,high,low);
    
    printf("\n(%d) calling merge");
    
    printf("\n(%d) calling merge mid=%d high=%d,low=%d\n",depth,mid,high,low);
    
    merge(a,low,high,mid);
    }
    return(0);
    }
    Pass 0 as the depth when you call it from main.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    4
    @Salem

    Thanks for the help you suggested by using a depth variable. Now i almost get it. I have one doubt though after the first call to void merge(); do the values get reset(i.e) before calling merge() the value of the depth variable was 1 and after calling merge() the value becomes 0 . Am i correct in thinking that after the first call the values sent to the merger_sort() are the old values instead of the values got by recursively splitting the array in the previous calls of merge_sort()???

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by touches View Post
    @Salem

    Thanks for the help you suggested by using a depth variable. Now i almost get it. I have one doubt though after the first call to void merge(); do the values get reset(i.e)
    No, what would that accomplish?

    before calling merge() the value of the depth variable was 1 and after calling merge() the value becomes 0.
    It's not clear exactly how the specific functions work in your example, since you didn't post them (maybe you should), but it appears to me that rather than having the function calls occur recursively (which they would in a real sort), this program demonstrates the sort by calling the functions manually a predetermined number of times (appropriate to the array size).

    Am i correct in thinking that after the first call the values sent to the merger_sort() are the old values instead of the values got by recursively splitting the array in the previous calls of merge_sort()???
    Again, would that not defeat the whole purpose? The idea is that merge_sort() splits the array in half each time, then merge() puts it back together. And the order of the number necessarily changes -- reseting the array would not make sense.

    There is a great animated gif of merge sorting the numbers 1-8 here:

    File:Merge-sort-example-300px.gif - Wikipedia, the free encyclopedia, from the article: Merge sort - Wikipedia, the free encyclopedia, which has further examples/diagrams/explanations.

    In that animated gif, merge_sort() would be called on the 8 member array once, splitting it into two four member arrays, then two more times recursively to split each four member array into 2 member arrays. You can optimize at this point to return a sorted 2 member array, altho that is not quite what happens in the pseudocode in the article (it splits until there is only one element and returns it). Then merge() combines each two member array into a four member array, then a final merge() creates the sorted 8 member array. How merge() combines the array works is easy to understand if you watch the animation.
    Last edited by MK27; 11-05-2011 at 02:34 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Nov 2011
    Posts
    4
    @MK27

    Yes the thought of resetting the values would defeat the purpose but i dont get how the values are stored in the recursive calls. I am posting the code and the output

    Code:
    array={4,1,7,3};
    
    int mergesort(int a[], int low, int high,int depth)
    {
    int mid;
    printf("\nlow=%d high=%d\n",low,high);
    if(low<high)
    {
    mid=(low+high)/2;
    
    printf("\n(%d) before mid mid=%d 
    
    high=%d,low=%d\n",depth,mid,high,low);
    
    mergesort(a,low,mid,depth+1);
    
    printf("\n(%d) before mid+1 mid=%d 
    
    high=%d,low=%d\n",depth,mid,high,low);
    
    mergesort(a,mid+1,high,depth+1);
    
    printf("\n(%d) after mid+1 mid=%d 
    
    high=%d,low=%d\n",depth,mid,high,low);
    
    printf("\n (%d) calling merge",depth);
    
    printf("\n (%d) calling merge mid=%d 
    
    high=%d,low=%d\n",depth,mid,high,low);
    
    merge(a,low,high,mid);
    }
    return(0);
    }
    
    Output:
    
    low=0 high=3
    
    (0) before mid mid=1 high=3,low=0
    
    low=0 high=1
    
    (1) before mid mid=0 high=1,low=0
    
    low=0 high=0
    
    (1) before mid+1 mid=0 high=1,low=0
    
    low=1 high=1
    
    (1) after mid+1 mid=0 high=1,low=0
    
     (1) calling merge
     (1) calling merge mid=0 high=1,low=0
    
    (0) before mid+1 mid=1 high=3,low=0
    
    low=2 high=3
    
    (1) before mid mid=2 high=3,low=2
    
    low=2 high=2
    
    (1) before mid+1 mid=2 high=3,low=2
    
    low=3 high=3
    
    (1) after mid+1 mid=2 high=3,low=2
    
     (1) calling merge
     (1) calling merge mid=2 high=3,low=2
    
    (0) after mid+1 mid=1 high=3,low=0
    
     (0) calling merge
     (0) calling merge mid=1 high=3,low=0
    
    sorted array:
    1
    3
    4
    7
    Here i would like to know how the depth variable becomes 0 after returning from calling merge()??

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by touches View Post
    Here i would like to know how the depth variable becomes 0 after returning from calling merge()??
    Because it is recursive. Consider this:

    Code:
    #include <stdio.h>
    
    void recurse (int a) {
    	if (!a) return;
    	recurse(a-1);
    	fprintf(stderr,"%d\n", a);
    }
    
    int main(int argc, const char *argv[]) {
    	recurse(5);
    	return 0;
    }
    The initial call to recurse() sets a as 5, then the recursion counts down to zero. But notice that the output does not occur until the recursive calls return. So do you think this will print:

    5 4 3 2 1

    or

    1 2 3 4 5

    If you guessed the first one, you're wrong. Try it and think about why; the depth count in your merge_sort() does the same thing.

    Recursive functions complete in reverse order; the first one to complete is the last one called, and the last one to complete is the first one called.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Nov 2011
    Posts
    4
    @MK27

    Thanks a lot for that snippet. It brought back memories of reading recursive function calls . Now i get why it acts the same in merge sort. Thanks a lot once again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ MergeSort
    By Jesse20ghet in forum C++ Programming
    Replies: 14
    Last Post: 06-15-2011, 01:24 PM
  2. my mergeSort
    By Soulzityr in forum C Programming
    Replies: 41
    Last Post: 03-29-2010, 12:27 PM
  3. Mergesort in C
    By Oduig in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 11:30 AM
  4. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  5. mergesort
    By AmazingRando in forum C++ Programming
    Replies: 14
    Last Post: 02-29-2004, 09:35 AM