# Divide-and-Conquer and Merge Sort

## Review Sorts

Bubble and Selection sort - always
O(*n*^{2}) - never use

Insertion sort - worst case O(*n*^{2})
but best case O(*n*) - use for small almost sorted arrays

Heap sort - always O(*n lg n*)

## Divide-and-Conquer

Divide and conquer is an algorithm, or design pattern, consisting
of three steps:

**Divide**: Divide the input
into sub-sets, unless the input size is small enough to solve
easily.

**Recur**: Recursively solve
the sub-sets problems.

**Conquer**: Merge the solution from the sub-problems.

The main idea of the divide and conquer design pattern is if the
problem is too large to solve easily then divide the problem into two
until it is small enough to solve. Naturally this is a
recursive algorithm, but doses not have to be implemented
recursively. As we come out of the recursive call we have to
merge the solutions from the sub-problems.

## Merge Sort

Assume the problem is a Sequence S of *n* unordered objects
and we want to return S sorted. Using the Divide and conquer
design pattern:

**Divide**: If S has one
element then trivial to solve and return S. Otherwise divide S
into two sequences S_{1} and S_{2} with *ceiling*(*n*/2)
and *floor*(*n*/2) elements respectively.

**Recur**: Recursively divide
S_{1} and S_{2}.

**Conquer**: Put back the elements into S by merging the
sorted sequences S_{1} and S_{2} into a sorted
sequence.

### Illustrate

using *merge-sort tree* form.

Note that the height of the merge-sort tree is 2 *lg n*.

### Merge

Merging is the hard part.

Assume that we have two sorted
sequences, S_{1} and S_{2}.

#### Illustrate

**Algorithm **merge**(**S_{1}, S_{2}, S):

*// input*: ordered sequences S_{1}
and S_{2}

*// output*: ordered sequence S containing
S_{1} and S_{2} elements.

**while**
S_{1} is not empty **and** S_{2} is not empty **do
**

**if**
S_{1}.first().element() <= S_{2}.first().element()
**then **

S.insertLast(S_{1}.remove(S_{1}.first()))

**else**

S.insertLast(S_{2}.remove(S_{2}.first()))

**while**
S_{1} is not empty **do **

S.insertLast(S_{1}.remove(S_{1}.first()))

**while**
S_{2} is not empty **do **

S.insertLast(S_{2}.remove(S_{2}.first()))

**Note** the time is O(*n*_{1} + *n*_{2})

#### Cost

Assume that inserting into first and last position is O(1), this
is true for circular array or link list.

Let *n* be the size of S, the initial unsorted sequence.
Let *v* be a node of the merge-sort tree, and *i* the depth
of the node. Then the size of the sequence is *n*/2^{i}.
The time spent at both the divide and conquer phase is proportional
to the size of the sequence at the node, O(*n*/2^{i}).
Note that each depth there are 2^{i} nodes. So
the total time spent at the *i*th depth is (time at each node,
O(*n*/2^{i}) )* ( number of nodes, 2^{i})
equal to *n*. Therefore the total time is (time at each
depth, *n*)*(height of the merge-sort tree, *lg n*) equal
to O(*n lg n*).