Recursion in c++ in the example of merge sort

Question

I have a very general question about recursion in c++. For a better understanding I use the following example of merge sort to explain my unsureness.

   void mergesort (int* first, int* last)
{
   int n = last - first;
   if (n<=1)return;
   int* middle = first + n/2;
   mergesort (first, middle);
   mergesort (middle, last);
   merge (first,middle, last);
}

where the function mergehas to be defined. The function arguments int* first,int* lastare to pointers pointing to the first and last element in an array respectively. Let say the array has length 10. Let's see what happens:

1. Since 10 is greater then 1, we declare a pointer int* middle = first + 5;.

Now my question: We are calling mergesort(first, middle), and this recursion will end as soon as we have split the first have of the array in single "elements". But is mergesort(middle,last) execute after mergesort(first,middle) has terminated or at the same time? Somehow it must be at the same time, otherwise we do not split up the second half into single "elements". Same question with merge sort in the last time. So how does recursion execute several function calls?

EDIT I've added the complete source code as well as an output:

//Mergesort.cpp
//

#include <iostream>
void merge (int* first, int* middle, int* last)
{
  int n = last - first;
  std::cout<<"merge part, n= " << n<<"\n";
  std::cout<<"merge part, middle= " << *middle << "\n";
  std::cout<<"merge part, last= "<<*last << "\n";
  int* deck = new int[n];

  int* left = first;
  std::cout<<"merge part, left = first " << *left<< "\n";
  int* right = middle;
  std::cout << "merge part, right = middle " << *right << "\n";
  for (int* d = deck; d!=deck+n;++d){
    if (left == middle) *d = *right++;
    else if (right==last ) *d=*left++;
    else if (*left < *right) *d = *left++;
    else *d = *right++;}

  int *d = deck;
  while (first != middle) *first++ = *d++;
  while (middle != last) *middle++ = *d++;

  delete[] deck;
}


void mergesort (int* first, int* last)
{
  int n = last - first;
  if (n <= 1) return;
  std::cout << "n= " << n;
  int* middle = first + n/2;
  std::cout << "first = "<< *first << "middle = "<< *middle<<"\n";
  mergesort (first, middle);
  mergesort (middle, last);
  merge (first, middle, last);
}

int main () 
{
  int a[4]={6,2,1,3};
  int* first = a;
  int* last = a+4;
  mergesort (first, last);
  std::cout<< a[0]<< a[1]<< a[2]<< a[3]<<"\n";
  return 0;
}

Output:

ThinkStation-S20:~/c++/test_files$ ./mergesort 
n= 4first = 6middle = 1
n= 2first = 6middle = 2
merge part, n= 2
merge part, middle= 2
merge part, last= 1
merge part, left = first 6
merge part, right = middle 2
n= 2first = 1middle = 3
merge part, n= 2
merge part, middle= 3
merge part, last= 4197792
merge part, left = first 1
merge part, right = middle 3
merge part, n= 4
merge part, middle= 1
merge part, last= 4197792
merge part, left = first 2
merge part, right = middle 1
1236

Answer 1

C++, like C, executes statements in order, one after another. So the second call to mergesort will occur after the first one returns. With an appropriate definition of merge, that will work just fine. I strongly suggest that you try the program yourself, simulating the computer with paper and pencil. It won't take you too long (honest!) and it should resolve your doubts.

Like quicksort, mergesort can be (partially) executed in parallel. The two recursive calls to mergesort are independent of each other so there execution could overlap. But C++ won't do that for you without quite a bit of extra work.

---

Here's one way to do this with pencil and paper, which I think is easier to understand than trying to interpret printf output.

1. Make about a dozen card-size papers.
2. Start with the first call to mergesort, from main.
3. Grab one of the cards, and fill in the four variables: first, last, middle, n.
4. Step through the lines of mergesort until you reach a new call. Write the line number of the call on the current card, put it on the "stack" (which starts off empty), and continue with step 3.
5. When you reach the end of mergesort, discard the current card and go back to the previous one, which will be on the top of the stack. Continue with step 4, starting with the next line in mergesort.
6. When you've done all the cards you started with, you're done.

Answer 2

Nothing happens at the same time, it helps to think of each successive function call as adding to a stack. At the end of the function it pops of the stack and continues.

http://www.youtube.com/watch?v=_r0gV2hQYf0