Merge Sort

Why is this important?

This workshop is important because:

Merge sort is the first fast, powerful sorting algorithm that you will encounter in the wilds of the real world (it's baked into Safari and Firefox!). It uses an extremely efficient application of the 'Divide and Conquer' concept to sort lists of elements. It's also a great chance to practice recursion.

What are the objectives?

After this workshop, developers will be able to:

• explain the three parts of a recursive algorithm.
• describe the merge algorithm and a merge sort algorithm.
• write a pseudocode version of merge sort and a draft version of merge sort in Ruby.
• determine the runtime (in big-O() notation) for merge sort.

Where should we be now?

Before this workshop, developers should already be able to:

• iterate through an array using a for loop, forEach, or other iterators.
• describe the purpose of big-O() notation.

Recursion

A recursive function is a function that calls itself. Recursive functions can have results that feel magical compared to the amount of code that's been written. For example look at this version of a factorial function in JavaScript:

function factorial(n):
  if (n === 0 || n === 1){
    return 1;
  }
  else {
    return n * factorial(n-1);
  }

Or in Ruby:

def factorial(n)
  if n == 0 || n == 1
    1
  else
    n * factorial(n-1)
  end
end

On the board, walk through this function with input of 1, 2, and 3 to find out what it returns.

Factorial uses the notation n!, pronounced "n factorial" (like 3! or 9001!). It is defined for whole numbers greater than or equal to 0 -- it means the result of multiplying n * (n-1) * (n-2) * ... * 3 * 2 * 1. You can probably think of an iterative way to write this with a for loop, but a recursive version can give us a little insight into recursion.

Warning: there's a whole lot of insight involved in generating the code above. On your first encounters with recursion, it might be pretty hard to imagine writing the code yourself. That's OKAY! Look at and closely study many examples and you'll get closer and closer to generating this stuff yourself.

Let's use factorial as an example to illustrate the three steps of a recursive algorithm:

function factorial(n):
  if (n === 0 || n === 1){
    return 1;
  }
  else {
    return n * factorial(n-1);
  }

1. Define base case(s) - make special case or cases to handle the simplest possible inputs without recursion. The base cases above are where n is 0 or 1. By definition, 0! and 1! are both just 1.
2. Make recursive call(s) - if you are not looking at a base case, recursively solve smaller subproblems to help find the answer to the main problem. In the example above, factorial(n-1) is the recursive call. It is a call to solve the subproblem of (n-1)!. We pick that as our subproblem because n! is equal to n*(n-1)!. For example 3! = 3 * 2!.
3. Phrase the returned value in terms of subproblem answer(s) - combine subproblem answers (the result of recursive calls) with any extra processing needed to pull out the final answer. In the example, multiplying the subproblem answer factorial(n-1) by n gives the final result. We want to make sure we return that result.

Check for Understanding

What's the Fibonnaci sequence?

1
1
2
3
5
8
13
...

Here's pseudocode for calculating the Fibonacci sequence:

fibonacci(n) {
   if (n === 1 or n === 0)
      return 1
   else
      return fibonacci(n-1) + fibonacci(n-2)
}

1. What base case(s) are covered?
2. What recursive subproblem(s) are solved?
3. What processing turns the answers from the subproblem(s) into an answer for the overall problem?

Now a more challenging example. Think about the same three questions for this binary search pseudocode:

binarySearch(array, target, low, high) {
  if (low > high)
     return -1;

  int mid = (low + high)/2;

  if (array[mid] == target)
     return mid;
  else if (array[mid] < target)
     return binarySearch(array, target, mid+1, high);
  else // last possibility: a[mid] > target
     return binarySearch(array, target, low, mid-1);
}

Merge Sort

Take a look at this video. Can you see how merge sort works?

Merge sort works on the basic principal of divide and conquer - dividing your list into sub-lists (recursively) until your sub-lists are of length one or zero. Once your sub-lists are at that size, you merge with a neighboring sub-list. When you merge them, you merge them in sorted order.

Divide Into Sub-lists

^{Merge Sort Visualization from University of Alberta}

Merge To Build Sorted List

^{Merge Sort Visualization from University of Alberta}

There are usually TWO algorithms that work together to accomplish a merge sort:

• A merging algorithm that takes two sorted arrays and combined them into one large sorted array pushing the lowest to highest valued elements. The merge algorithm is not recursive.

• A merge sort algorithm that takes an array, splits it into two halves, recursively merge sorts both halves, and finally uses the merge algorithm to put them back together into one sorted array.

Note: iterative merge sort is possible, but it's much harder. Please work on a recursive version!

Runtime efficiency analysis

To try to figure this out, let's try a few methods.

1. On the graph below what are the realistic possibilities for the runtime of this algorithm?

2. How "tall" is the diagram below? That is, how many times do we divide and how many times do we "conquer"?

3. How "wide" is it? That is, how many steps are, roughly, there in each divide/conquer step?

Make your own merge sort implementation!

Goal: Write a merge function and a mergeSort function to implement recursive merge sort as described above.

1. Start with the recursive mergeSort -- assume you have a working merge function. Consider:

• What base case(s) do you need for mergeSort?
• What smaller subproblems can you solve recursively?
• How will you go from the solutions for subproblems, to a solution for the overall problem?

1. Next, tackle merge. This isn't recursive, but edge cases can make it tricky!

Additional Resources

• Merge sort on wikipedia
• Calculating Big O for recursion from MIT
• Graphical comparison of sorting algorithms