# Merge Sort

**Introduction**

Merge sort is one of the famous sorting algorithms. Merge sort works on simple premise of divide and conquer. In this blog we will discuss about Merge sort and get a brief idea about notion of divide and conquer.

**Divide and Conquer**

Divide and conquer is an approach where we divide a large problem into smaller, easier to solve sub problems. Results of these smaller sub problems can be combined to give the final answer.

The Divide and Conquer approach is based on three main concepts:

**Divide:**Divide a problem into small sub problems**Conquer:**Conquer sub-problems by solving them recursively.**Combine:**Combine the answers of these sub problem and merge them to get the answer of original problem

Now let’s understand one of the application of divide and conquer approach and one of the most common sorting technique i.e. Merge sort.

**Merge Sort**

The main idea behind merge sort is to divide the array or list to be sorted into smaller sub arrays or sub lists. Here we sort and combine these sub lists or sub arrays recursively to get the sorted array or list for the given original unsorted list or array.

Let’s see in detail how we will use three main aspects of divide and conquer approach (Divide, Conquer, Combine) in the merge sort algorithm.

Suppose we have an array *Arr**.* We have to sort this ** Arr** using merge sort. Using divide and conquer approach ,instead of sorting the whole array we will sort two smaller sub arrays. Let the starting index of array be

**and ending index be**

*start***, then above array can be represented as**

*last***.**

*Arr[start , last]***Divide:**

Let mid be the middle point of the array then we can split our original array ** Arr[start , last]** into two smaller sub arrays that is

**and**

*Arr[start , mid]*

*Arr[mid+1 , last].***Conquer:**

In this step, we will sort the two subarrays** Arr[start , mid]** and

**if best case is reached. If not ,then we again divide both these subarrays and try to sort them.**

*Arr[mid+1 , last]***Combine:**

When we get our two sorted subarrays ** Arr[start,mid]** and

**from the conquer step , then we can combine both these sorted arrays to get the result which is sorted array**

*Arr[mid+1,last]*

*Arr[start , last].*As mentioned earlier we will continue to divide till best case is reached. Now what is this best case. The best case we take is when sub arrays have only one element. This is because array having only a single element is already sorted. That’s why we will continue to divide array and consequent sub arrays till a case is reached when the subsequent subarray will have only one element.

**Implementation of Merge Sort Algorithm:**

We will use two function ** Sort()** and

**. Sort function will divide the array into two half arrays till we reach a stage when subarrays have only one element i.e. (**

*Merge()***==**

*start***). After this Merge function starts running and combines these sorted sub arrays into a larger sorted array. This will continue till the whole array is merged.**

*last***Sort function code:**

*Sort (int Arr[], int start, int last)* {

*If (start >= last) {*

*return;*

*}*

*int mid= (start + last)/2;*

*Sort (Arr, start, mid);*

*Sort (Arr, mid+1, last);*

*Merge (Arr, start, mid, last);*

*}*

Now after divide step, our task is to merge two sorted subarrays into a single sorted array. We will use merge function for this.

## Code for merge function:

*void merge (int Arr[], int start, int last, int mid)*

*{*

*int n1 = mid — start + 1;*

*int n2 = last — mid;*

*// Create two temporary arrays temp_1 ->Arr[start,mid] and temp_2 ->Arr[mid+1, last]*

*int temp_1[n1], temp_2[n2]*

*for (int i = 0; i < n1; i++)*

*temp_1[i] = Arr[start + i];*

*for (int j = 0; j < n2; j++)*

*temp_2[j] = Arr[mid + 1 + j];*

*// Merge the temporary arrays back into Arr[start,end]*

*// Now we will keep track of indices of temporary sub arrays and of the merged subarray*

*// Initial index of first subarray*

*int i = 0;*

*// Initial index of second subarray*

*int j = 0;*

*// Initial index of merged subarray*

*int count = start;*

*while (i < n1 and j < n2) {*

*if (temp_1[i] <= temp_2[j]) {*

*Arr[count] = temp_1[i];*

*i++;*

*}*

*else {*

*Arr[count] = temp_2[j];*

*j++;*

*}*

*count++;*

*}*

*// Copy the remaining elements of temp_1 array, if there are any*

*while (i < n1) {*

*Arr[count] = temp_1[i];*

*i++;*

*count++;*

*}*

*// Copy the remaining elements of temp_2 array, if there are any*

*while (j < n2) {*

*Arr[count] = temp_2[j];*

*j++;*

*count++;*

*}*

*}*

## Explanation of Merge function:

- Create copies of the subarrays
and*temp_1 -> Arr[start,mid]**temp_2 -> Arr[mid+1,last].* - Create three pointers
and*i,j*.*count* maintains current index of*i**temp_1.*maintains current index of*j*and*temp_2*maintains current index of*count**Arr[start,last].*- Now looping will continue till it reaches end of
or*temp_1*.*temp_2* - In each iteration of loop, we pick the smaller among elements of
and*temp_1*and place it in correct position.*temp_2* - When we come out of loop (elements of either
or*temp_1*have run out) pick up the remaining elements and put them in*temp_2**Arr[start,last].*

Now lets us see functioning of merge function using an example

Let us see how merge function will merge the two arrays.

## Step 1:

create copies of sorted sub arrays to be merged.

int n1 = mid — start + 1;

int n2 = last — mid;

*// Create two temporary arrays temp_1 ->Arr[start,mid] and temp_2 ->Arr[mid+1, last]*

int temp_1[n1], temp_2[n2]

for (int i = 0; i < n1; i++)

temp_1[i] = Arr[start + i];

for (int j = 0; j < n2; j++)

temp_2[j] = Arr[mid + 1 + j];

## Step 2:

Maintain index of sub-arrays and main array

*// Initial index of first subarray*

int i = 0;

*// Initial index of second subarray*

int j = 0;

*// Initial index of merged subarray*

int count = start;

## Step 3:

Now looping will continue till it reaches either of temp_1 or temp_2. In each iteration of loop, we pick the smaller among elements of temp_1 and temp_2 and place it in correct position.

while (i < n1 and j < n2) {

if (temp_1[i] <= temp_2[j]) {

Arr[count] = temp_1[i];

i++;

}

else {

Arr[count] = temp_2[j];

j++;

}

count++;

}

## Step 4:

When it comes out of loop (elements of either temp_1 or temp_2 have run out) pick up the remaining elements and put them in Arr[start,last]

*// Copy the remaining elements of temp_1 array, if there are any*

while (i < n1) {

Arr[count] = temp_1[i];

i++;

count++;

}

*// Copy the remaining elements of temp_2 array, if there are any*

while (j < n2) {

Arr[count] = temp_2[j];

j++;

count++;

}

At the end of the merge function, the array Arr[start,last] is sorted.

**Complexity of Merge Sort:**

Using Sort() function we are dividing our array into two subarrays and we continue to do this with each subarray till best case is reached. Hence complexity of merge function is *O(log n). **W*e are also merging these sorted sub arrays using merge function which has a complexity of ** O(n)**. Hence complexity of merge sort algorithm is

**or**

*O((log n) x n)*

*O(n log n)*