Merge Sort

Merge sort takes advantage of the fact that it is easy to merge two already sorted data sets – all you have to do is compare the first two values in each set to determine which is earlier in the sequence. Merge sort makes use of a widely used programming technique called recursion.

Recursion is when a function calls itself to accomplish a task (it may also involve two functions calling each other – this is called mutual recursion). Recursion actually takes advantage of the way that function calls and return addresses use a stack (LIFO) structure – when a function returns the address that execution continues at is popped from a stack.

The classical example of recursion is the calculation of factorial numbers. Factorial 3 (written as 3!) is the product of itself and all of the positive integers less than itself.  This can be written as 3 * 2 * 1. It can also be written as 3 * 2! We can take advantage of this to help us compute factorial numbers. There is a base case where we know that 1! = 1, and that for all of the other values we can say that n! can be rewritten as n * (n-1)!

This can be shown in pseudocode as:


function fact(n)
{
   if (n<=1)
      return 1;
   else
      return n * fact(n-1);
}

If we call the function with a value of 1, then the value 1 will be returned. If we call the function with a value of 2, then the following sequence of events will take place:

  1. Instance 1 of the function will be started, with a value of f = 2
  2. The test will be made to see if f is equal to 1. f is not equal to 1, so the else branch is executed
  3. This code will attempt to evaluate the expression f * fact (f-1)
  4. In order to evaluate the expression we need to calculate fact (f-1)
  5. Instance 2 of the function will be started, with a value of 2-1 ( 1 )
  6. The test will be made to see if f is equal to 1. f is equal to 1, so 1 is returned to the calling function (in this case instance 1)
  7. Instance 1 can now calculate 2 * 1
  8. Instance 1 can now return the value 2 to the calling function

Recursion works by dividing the problem up into smaller pieces until it reaches a ‘base case’ when the problem can be solved easily (in the case of the factorial problem the base case is when we want to calculate factorial 1). It is a remarkably useful technique, but care is required to ensure that the base case can be reached. If the base case cannot be reached, then the recursion will be infinite, causing such unpleasant symptoms as machine slowdowns or crashes.

Next: Merge Sort 2