The Merge Sort algorithm belongs to the family of efficient sorting algorithms, whose average complexity is the best that we can find **O**(*n *log(*n*)). It is an example of divide and conquer method. Through this method we are going to solve a problem recursively, applying three steps of recursion

**Divide**the problem into a number of small subproblems.**Conquer**the subproblems by resolving them recursively.**Combine**the solution of each subproblem into the solution for the original problem.

## Review

Name |
Merge Sort |

Best case |
O(n log(n)) |

Average case |
O(n log(n)) |

Worst case |
O(n log(n)) |

Difficulty |
Medium |

Family |
Efficient sorts |

## Algorithm

If the subproblem is large enough to solve recursively we call that recursive case, when there is no longer recursion we call it the base case. In particular:

**(Base case) **If the sequence length is between 0 and 1, it's ordered.

**(Divide) **Else we divide the sequence into two half subsequence. If the number of elements is odd, one subsequence will have one more element.

**(Conquer) **Each of these sequences will be ordered, applying recursively the algorithm.

**(Combine) **Then the subsequence will be combined, in order to do that we take repeatedly the minimum and we put that into the output sequence, that will be ordered.

The algorithm was invented by John von Neumann in the year 1945.

## How does it work

Let's consider an array A and divide it into *n* subarray (A_{1, }A_{2,...}A_{n}) until we obtain the A_{n} array with only one element.

We start with the array A

Then we split it into two subarrays: left subarray and right subarray

We go on splitting since the length of the subarray is greater than 1...

Now it's time to Merge!

We are going to merge recursively each subarray to produce a newly sorted subarray.

In this way, subarrays are merged to produce a longer sorted subarray until we reach the sorted array.

At each step of Merge we:

- Compare the first element of the subarray A and the first element of subarray B.
- Select the smallest element
- Insert it into the resulting array

For example, let's consider subarray** A = { 2, 8, 11}** and subarray **B = { 5, 6, 28}** with three element each one.

We have to obtain the ordered resulting array **R = { 2, 5, 6, 8, 11, 28}**.

Let's apply the merge algorithm and see what's happening:

## Pseudocode

Generalizing we can distingue two phases:

**Split phase**

- If the (sub)array has length 1--> stop the split phase
- If the (sub)array has length > than 1 --> split in two parts (left and right)

`function mergeSort(array)`

`//If the length(array)=1 --> stop the split phase`

`if(lenght(array)==1)`

`return array`

`//Else split in two parts (left and right), go ahead splitting and then Merge`

`else`

`split(array) = [left, right];`

`left = mergeSort(left)`

`right = mergeSort(right)`

`array = Merge(left, right)`

`return array`

**Merge phase**

Merge the left and right (sub)array into a unique ordered array.

`function Merge(left, right)`

`//Merge the list until at least one of them is empty`

`while notEmpty(left) and notEmpty(right)`

`//If the element of the array left is less or equal to the first of right, put it in the result array`

`if first(left) <= first(right)`

`append first(left) to result`

`//Else put the first right array element in the result array`

`else `

`append first(right) to result`

## Programming languages implementation

**C++**

We are going to write two functions.

**mergeSort**

```
void mergeSort(int array[], int first, int last){
//If the array contains only one element stop splitting
if(first>=last)
return;
//Else go ahead splitting
//Find the approximate middle
//This formula is equal to (first+last)/2
//But avoids overflow for large first and last
int middle = first + (last-first)/2;
//Go ahead splitting the left side
mergeSort(array, first, middle);
//Go ahead splitting the right side
mergeSort(array, middle+1, last);
//Then merge them
merge(array, first, middle, last);
}
```

**merge**

```
void merge(int array[], int first, int middle, int last){
//Calculate the lenth of the support array tmp
int length = last-first+1;
int tmp[length];
int startLeft = first;
int startRight = middle+1;
for(int i = 0; i<length; ++i){
if(startLeft>middle){
tmp[i] = array[startRight++];
}
else if(startRight>last){
tmp[i] = array[startLeft++];
}
else if(array[startLeft]<=array[startRight]){
tmp[i] = array[startLeft++];
}
else{
tmp[i] = array[startRight++];
}
}
for (int m=0; m< length; ++m){
array[first++] =tmp[m];
}
}
```

There are various ways to implement the Merge Sort algorithm.

Try to implement it by yourself!

**Complete program**

```
//
// MergeSort - Array Implementation - C++
//
// Created by Andrea Cappelletti on 10/04/2018.
//
// Explanation: https://www.cmprogrammers.com/post.php?id=51
#include
//Define the constant size of the array
#define size 5
//Function Merge that combine the processed array
void merge(int array[], int& first, int& middle, int& last){
int length = last-first+1; //Calculate the length of the support array tmp
int* tmp = new int[length]; //Inizialize tmp
int startLeft = first; //Save the initial index of the left side array
int startRight = middle+1; //Save the initial index of the right side array
for(int i = 0; i<length; ++i){ //Let's fill the ordered array tmp with a for cicle
if(startLeft>middle){ //We have finished to fill the right side of the array
tmp[i] = array[startRight++];
}
else if(startRight>last){
tmp[i] = array[startLeft++]; //We have finished to fill the left side of the array
}
else if(array[startLeft]<=array[startRight]){ //Each time we are going to add the minimum element
tmp[i] = array[startLeft++]; //The left element is the least
}
else{
tmp[i] = array[startRight++]; //The right element is the least
}
}
//Let's save the ordered array and delete tmp
for (int m=0; m< length; ++m){
array[first++] =tmp[m];
}
delete [] tmp;
}
//This is the recursive function
void mergeSort(int array[], int first, int last){
if(first>=last) //Base case
return;
int middle = first + (last-first)/2; //Calculate the middle of the array (avoiding the overflow)
mergeSort(array, first, middle); //Let's call the function recursively
mergeSort(array, middle+1, last);
merge(array, first, middle, last); //And then...merge!
}
//This function allow us to print the array so we can check if the merge was successfull
void print(int array[]){
for(int i = 0; i< size; i++){
std:: cout <<array[i]<<" ";
}
std::cout<<std::endl;
}
//Main
int main(){
int array[size]={4,6,3,2,1}; //Let's fill our array of size defined in the beginning of the file
std::cout<<"Array before mergeSort"<<std::endl;
print(array);
mergeSort(array, 0, size-1);
std::cout<<"Array after mergeSort"<<std::endl;
print(array);
}
```

The full code is available on my GitHub

## Properties

The Merge Sort is the best sorting algorithms for a large amount of data.

It is a stable algorithm, but it's not adaptative.

We can use it in every situation, in particular when we want to order linked list and when random access is much more expensive than sequential access.

## Complexity

The merge sort is a really efficient algorithm for a large amount of input.

The time complexity can be expressed as following recurrence relation

The complexity is Θ(*n *log(*n)*) in each case (average, worst, best).