// Sorts the sequence (A[p],...,A[r-1])
template<class T> 
void merge_sort(array<T>& A,int p,int r) 
{ 
  if (p<r-1)     
  { 
     int q=?; // see discussion in the text
     merge_sort(A,p,q);
     merge_sort(A,q,r);
     merge(A,p,q,r);
  }
}

Let's say array is [4, 9, 13, 1, 5]. I understand the recursion, the first merge_sort method splits the array up until the point of [4], so the first and second merge sort method gets skipped.How does it know where the rest of the array is to merge it? Array A is now only [4], so if we call merge (A,p,q,r) it only gets the 4 and no other part of it to merge it with?

CodePudding user response：

Array A is now only [4] ... it only gets the 4 and no other part of it to merge it with.

That's were the confusion is. The array doesn't get shorter! At all times the array is the complete array with all its original values.

The notion of a subarray is only reflected by the additional parameters, p and r. These mark the range of interest in that full array (where p is the first index that is in the range, and r is the first index after the range).

Look for instance, at this recursive call:

 merge_sort(A,p,q);

The p and q indices mark where in the array A is the partition that we want to sort. That call will only work with that part of the array.

At a certain moment, we will have p==0, q==1 and r==2 and the above call will then look at one element only, A[0].

The next recursive call is:

 merge_sort(A,q,r);

This call will also look at one element: A[1].

These two calls will just return (as obviously nothing had to be done as a subarray with just one value is always "sorted"), and then the merge can be done with this call:

 merge(A,p,q,r);

Note that this merge call gets to work with two values: A[0] and A[1]. When this call returns we know that the values at indices 0 and 1 are now guaranteed to be in sorted order.

CodePudding user response：

The merge_sort method recursively splits the array until each subarray contains only one element. Each subarray is considered to be "sorted" because it has only one element. The merge method then takes two "sorted" subarrays (which may originally have been part of the larger array) and merges them back together in sorted order. In the example you provided, after the initial call to merge_sort with the array [4, 9, 13, 1, 5], the array will have been split into subarrays [4] and [9, 13, 1, 5]. The merge method will then be called to merge [4] and [9, 13, 1, 5] back together in sorted order. The merge method keeps track of the indices of the start, middle and end of the subarrays being merged, so it knows which elements to merge together.