Merge Sort

Note

Objectives

1. Trace the recursive execution of merge sort.
2. Identify a run of merge sort on an array.

Code: Merge.java

Cool: Nonverbal instructions for Merge Sort

Both selection sort and insertion sort have worst case quadratic order of growth, and relied on iterative improvement where a sorted elements portion was maintained at the front of the sequence at all times. Merge sort represents a different approach to sorting based on the idea of recursion.

Important

Review the merge operation (merge sort's namesake), which takes two sorted arrays and returns a sorted result containing all the elements in both arrays.

Merge sort is a recursive sorting algorithm that can be described as follows.

1. If the array is of size 1, return.
2. Recursively merge sort the left half.
3. Recursively merge sort the right half.
4. Merge the two sorted halves.

Watch the following video through the 5:39 mark.

The recurrence relation for the runtime of merge sort can be given as $T(N) = T(N / 2) + T(N / 2) + N + 1$. The first recursive call to $T(N / 2)$ represents the time it takes to merge sort the left half while the second call represents the time it takes to merge sort the right half. But we could also state it more simply as just $T(N) = 2T(N / 2) + N$ because the runtime is the same regardless of which half we're discussing.

Recurrence diagrams

Unrolling this equation ends up producing a mess of parentheses and brackets, so let's try drawing a recurrence diagram to explain what's going on and use visuals to help organize our analysis. In a recurrence diagram, the recursive work is drawn as nodes (with the current subproblem depicted inside the node) while the non-recursive work is drawn beside the node. If we can add up all of the non-recursive work (numbers outside the node), then we've computed the total work done by the algorithm.

Here's an example of a recurrence diagram for merge sort on a 64-element array.

• The top layer takes about 64 units of time merging 2 sorted halves of 32 elements each.
• The second layer also takes about 64 units of time merging 4 sorted halves of 16 elements each.
• The third layer also takes about 64 units of time merging 8 sorted halves of 8 elements each.
• And on and on until the algorithm reaches its base case.

By identifying the pattern in the recurrence diagram, we can see that all the nodes that are on the same layer will take about 64 units of time. Since the entire runtime of merge sort is represented by this diagram, we can find the total time spent by multiplying the number of layers by the time spent on each layer. If we think about the problem more generally in terms of the size of the current subproblem $N$, then:

• Each layer divides $N$ in half until the base case of 1 element. Therefore, there are $\log_2 N$ layers.
• Each layer takes about $N$ total non-recursive time.
• Therefore, the runtime of merge sort is in $\Theta(N \log N)$

We call this $N \log N$ order of growth linearithmic (a portmanteau of "linear" and "logarithmic").