Search code examples
mergemergesort

Merge sort recursions

I have a problem. I started to learn how merge sort works, and now I'm stuck. I don't understand second recursion in merge function. 

int merge_sort(int input[], int p, int r)
{
      if ( p >= r ) return 0; 

        int mid = floor((p + r) / 2);
        merge_sort(input, p, mid);
        **merge_sort(input, mid + 1, r);** 
        merge(input, p, r);
}

When first recursion is finished, I end up with something like this: Original array: 3 4 5 6 7 8

3 4 5 | 6 7 8

3 4 | 5

3 | 4

3

And then second recursion starts. So, my question is: does second recursion starts from array with only one element ( array with only one number, 3 in this case) or from original array ( 6 element array from beginning)? I hope you will understand what I mean. Thanks.

Solution

  • i can't tell from your code because you are always passing the input array. But yes the idea is to divide and conquer so the first call should be with

    merge_sort: 3 4 5 6 7 8

    first recursion: 3 4 5

    second recursion: 6 7 8

    Take a look at this wikipedia picture: http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg