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.
