Merge Sort and the Divide and Conquer Approach

Algorithm Design Techniques

In earlier posts, I went through the insertion sort and the selection sort algorithms.  They both use the incremental approach.  Each step of the algorithms sorts one element, and thus the algorithms solve the problem incrementally.

The divide-and-conquer is another approach.  It includes 3 steps that are executed recursively until the problem is solved:

1. Divide the problem into smaller instances of the same problem.
2. Conquer or solve the smaller problems.
3. Combine the solutions to the smaller problems into the solution for the original problem.

Merge Sort

The merge sort follows the divide-and-conquer approach closely.  See section 2.3.1 of Introduction to Algorithms.  In each recursion step, a merge sort operates the following 3 steps:

1. Divide the n-element sequence to be sorted into two sub-sequences of n/2 elements each.
2. Sort the two sub-sequences by comparing the two top elements recursively.
3. Merge the two sorted sub-sequences to produce the sorted answer.

Clearly, the merge sort uses the divide-and-conquer approach because it involves applying the algorithm recursively following the divide-and-conquer steps.

The merge algorithm merges two sorted lists into one by comparing the front elements of each list.  The smaller element (if the two elements are the same, then either element) gets appended to the one new sorted list.  Repeat this until one of the list is empty.  The non-empty list is appended to the new sorted list.  After this point the two sorted lists are now merged into one.

Analyzing Divide-and-Conquer Algorithms

Because algorithms that take a divide-and-conquer approach are recursive in nature, we describe their running times by a recurrence equation or recurrence.  We look at the 3 steps (divide-conquer-combine) of an algorithm and derive the recurrence by adding the running times for each step.  Let T(n) be the running time on a problem of size n.  In merge sort the recurrence is

1. Divide the problem into 2:
   • Running time: constant
   • Number of executions: 1
   • Recurrence: Θ(1)
2. Sort the two sub-sequences:
   • Running time:T(n/2)
   • Number of executions:2
   • Recurrence: 2T(n/2)
3. Merge the two sorted sub-sequences:
   • Running time: Θ(n)
   • Number of executions: 1
   • Recurrence: Θ(n)

Therefore, the recurrence for a merge sort when n > 1 is

Θ(1) + 2T(n/2) + Θ(n) = 2T(n/2) + Θ(n)

because Θ(1) + Θ(n) = Θ(n).

Bam!  We got a sort algorithm that runs much faster than insertion sort!  Cool right?  Let’s code it in OCaml in both imperative and functional style!