### 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:

**Divide**the problem into smaller instances of the same problem.**Conquer**or solve the smaller problems.**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:

**Divide**the n-element sequence to be sorted into two sub-sequences of n/2 elements each.**Sort**the two sub-sequences by comparing the two top elements recursively.**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

**Divide**the problem into 2:- Running time: constant
- Number of executions: 1
- Recurrence:
**Θ(1)**

**Sort**the two sub-sequences:- Running time:T(n/2)
- Number of executions:2
- Recurrence:
**2T(n/2)**

**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!

## Leave a Reply