# Merge sort

Merge-sort is based on the divide-and-conquer paradigm. It involves the following three steps:

- Divide the array into two (or more) subarrays
- Sort each subarray (Conquer)
- Merge them into one (in a smart way!)

**Example**. Consider the following array of numbers

27 10 12 25 34 16 15 31

- divide it into two parts

27 10 12 25 34 16 15 31

- divide each part into two parts

27 10 12 25 34 16 15 31

- divide each part into two parts

27 10 12 25 34 16 15 31

merge (cleverly-!) parts

**10 27 12 25 16 34 15 31**

- merge parts

10 12 25 27 15 16 31 34

- merge parts into one

10 12 15 16 25 27 31 34

How do we merge two sorted subarrays? We define three references at the front of each array.

#### Complexity of Mergesort

Suppose T(n) is the number of comparisons needed to sort an array of n elements by the MergeSort algorithm. By splitting an array in two parts we reduced a problem to sorting two parts but smaller sizes, namely n/2. Each part can be sort in T(n/2). Finally, on the last step we perform n-1 comparisons to merge these two parts in one. All together, we have the following equation

`T(n) = 2*T(n/2) + n - 1`

The solution to this equation is beyond the scope of this course. However I will give you a resoning using a binary tree. We visualize the mergesort dividing process as a tree