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:

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

An algorithm devised by using divide and conquer approach

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.

An example of merge sort algorithm

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 start and ending index be last, then above array can be represented as 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 Arr[start , mid] and Arr[mid+1 , last].

Conquer:

In this step, we will sort the two subarrays Arr[start , mid] and Arr[mid+1 , last] if best case is reached. If not ,then we again divide both these subarrays and try to sort them.

Combine:

When we get our two sorted subarrays Arr[start,mid] and Arr[mid+1,last] from the conquer step , then we can combine both these sorted arrays to get the result which is sorted array 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 Merge(). Sort function will divide the array into two half arrays till we reach a stage when subarrays have only one element i.e. (start==last). 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.

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:

1. Create copies of the subarrays temp_1 -> Arr[start,mid] and temp_2 -> Arr[mid+1,last].
2. Create three pointers i,j and count .
3. i maintains current index of temp_1.
4. j maintains current index of temp_2 and count maintains current index of Arr[start,last].
5. Now looping will continue till it reaches end of temp_1 or temp_2.
6. In each iteration of loop, we pick the smaller among elements of temp_1 and temp_2 and place it in correct position.
7. When we come 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].

Now lets us see functioning of merge function using an example

Let us take sorted sub arrays Arr1 -> Arr[0,2] and Arr2 -> Arr[3,5]

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;

index of sub-arrays and main array

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). We are also merging these sorted sub arrays using merge function which has a complexity of O(n). Hence complexity of merge sort algorithm is O((log n) x n) or O(n log n)