Merge Sort Algorithm

In this tutorial, we will learn about a new sorting algorithm known as merge sort that has a far better performance than the sorting algorithms we have seen so far. Previously, we have looked upon simpler sorting algorithms including selection, bubble and insertion sort which were slower as compared to merge sort. This sorting algorithm uses the basic logic of recursion and uses it to effectively sort a list in an incredibly faster manner.

Understanding Merge Sort

Let’s see how to sort a list of integers given to us in a form of an array. Suppose we have an array of 7 integers named X with unordered numbers. Our aim is to sort the following numbers in increasing order of values by using a merge sort algorithm.

Merge Sort picture 1

Now the first thing we will do is to divide this list in two halves. If the list has a total number of elements equal to an even number then the list can will be split into exact two halves. However, if the list has a total number of elements equal to an odd number then you can choose which side to include the middle number in. This will result in one side having more elements than the other.

For our array we have 7 elements hence we will not have two equal sides. We can either split the array by placing the middle number which is 2 in our case, in the first half or in the second half. In either cases, one part of the array will have higher number of elements than the other.

Supposing we are splitting our array as shown below:

We have split the array ‘X’ into two arrays: ‘L’ denoting the left array and ‘R’ denoting the right array.

Merge Sort picture 2

Our approach will be to first sort these individual arrays “L’ and ‘R’ and then merge them together in the original array ‘X’ in a sorted order.

Merge Sort picture 3

Notice that all the elements in X are either present in L or R. Therefore we can start overwriting X from right to left. We will start at from index 0 in X. At any point, the smallest element will be either the smallest unpicked in L or the smallest unpicked in R. The figure below shows the smallest unpicked in both the sub arrays L and R in white.

Merge Sort picture 4

In ‘L’ the smallest element is 1. In ‘R’ the smallest element is 3. Now out of these two, the smallest is 1. This suggests 1 belongs to index 0 of X. Therefore, we will write 1 at index 0.

Merge Sort picture 5

Now we will look for the second smallest number in both the subarrays and so on and will write their values at the appropriate positions in X.

Pseudocode for Merge logic

Lets write a pseudocode to merge the two sorted arrays L and R into X. We will create a function called Merge() which will take in three arguments. The arguments will be L denoting the left subarray, R denoting the right subarray and X denoting our array in which the other two arrays will be merged.

Merge(L,R,X){
}

Then we will create two variables one that will store the elements in L and another that will store the elements in R. These could also be used as arguments for our Merge() function.

Merge(L,R,X)
{
 nL=length(L)
 nR=length(R)

Next we will define three more variables called i, j, and k and set them to zero initially. Here ‘i’ denotes the index of the smallest unpicked in L, ‘j’ denotes the index of the smallest unpicked in R, and ‘k’ denotes the index of the position that needs to be filled in X.

Merge(L,R,X)
{
 nL=length(L)
 nR=length(R)
 i=j=k=0


Lets show the stage where we had filled the smallest element at index 0 in X and were looking for the element to be placed at index 1, the ‘i’, ‘j’ and ‘k’ will be as follows:

i =1, j=0 and k=1. This is because the first element has been filled at this stage. The green coloured cell denotes the picked element that was the smallest of the two un picked elements now placed at index 0 in X.

Merge Sort picture 6

For i and j to be valid, they should be less than the number of elements in their respective arrays. Hence we will add the following while statement to our code:

Merge(L,R,X)
{
 nL=length(L)
 nR=length(R)
 i=j=k=0
 while(i<nL && j<nR)

Now inside the while statement, if L[i] is less than or equal to R[j], then for the array X at its k-th position we will overwrite it with L[i]. Here what we did was we compared the smallest unpicked element in the sub array L with that of the sub array R. If it was indeed smaller then that element will be placed at the k-th position in X. Additionally, we will increment both k and i to move to the next element.

Merge(L,R,X)
{
 nL=length(L)
 nR=length(R)
 i=j=k=0
 while(i<nL && j<nR)
{   if (L[i]<=R[j])
   {  X[k]=L[i]
      k=k+1
      i=i+1
   } 

If this condition is not true in the case that R[j] is smaller than L[i] then we will overwrite the k-th position of array X with R[j]. Additionally, we will increment both k and j to move to the next element.

Merge(L,R,X)
{
 nL=length(L)
 nR=length(R)
 i=j=k=0
 while(i<nL && j<nR)
{   if (L[i]<=R[j])
   {  X[k]=L[i]
      k=k+1
      i=i+1
   } 
    else
    { X[k]=R[j]
      k=k+1
      j=j+1
    }

Testing the Merge Logic

Let us demonstrate how the following pseudocode will work using our example array X.

Look at this stage shown below:

Merge Sort picture 6

Both i and j are valid numbers hence we will enter the while loop and check whether L[i] <= R[j] or not. L[i] in this case is 2 and R[j] is 3. 2 is lesser than 3 hence X[k] will now be 2. Moreover both k and i will get incremented by 1 as shown below. k moves to index 2 and i moves to index 2 as well.

Merge Sort picture 7

Now again we will check if L[i] <= R[j] or not. In this case, L[i]=4 and R[j] =3. As R[j] < L[i] we will move in the else statements and thus X[k] will be overwritten by 3. Increment both k and j to move ahead.

Merge Sort picture 8

Again we will check if L[i] <= R[j] or not. In this case, L[i] = 4 and R[j] =6. As L[i] < then R[j], hence X[k] will be overwritten by L[i]. Now in array X at index 3 we have the placed the element 4. Increment both i and k.

Merge Sort picture 9

Again we will check if L[i] <= R[j] or not. In this case, L[i] = 3 and R[j] =6. As L[i] < then R[j], hence X[k] will be overwritten by L[i]. Now in array X at index 4 we have the placed the element 5. Increment both i and k.

Merge Sort picture 10

Modifying the Merge pseudocode

As you may notice now at this stage i=3, j=1 and k=5. We have used all the elements from the sub array L and now it is at index 3 which is not valid inside our while condition. The condition where i<nL is not valid any more hence we will now pick elements from the other array to fill the remaining positions of X. Therefore we will have to include two additional while statements in our program to cater to this scenario where one of the subarrays gets exhausted. This is shown below:

Merge(L,R,X)
{
 nL=length(L)
 nR=length(R)
 i=j=k=0
 while(i<nL && j<nR)
{   if (L[i]<=R[j])
   {  X[k]=L[i]
      k=k+1
      i=i+1
   } 
    else
    { X[k]=R[j]
      k=k+1
      j=j+1
    }
while(i<nl)
{ X[k]=L[i]
  i=i+1
  k=k+1
}
while(j<nR)
{X[k]=R[j]
 j=j+1
 k=k+1
}

Once we are out of the first while loop then out of the two other while loops only one will execute. This is because out of the two sub arrays only one will have elements left. Now for our particular example the third while loop where j<nR will execute. Thus the remaining positions in X will be filled appropriately.

Merge Sort picture 11

Now we have all elements in the array X in a sorted arrangement.

Merge Sort picture 12

Sorting the Sub arrays

As you may remember we split the array ‘X’ into two sub arrays: ‘L’ denoting the left array and ‘R’ denoting the right array.

Merge Sort picture 2

Then we said that we will first sort these individual arrays “L’ and ‘R’ and then merge them together in the original array ‘X’ in a sorted order.

Lets see how to sort the subarrays L and R. We will further divide the subarrays L and R. Array L consists of 4 elements hence we will divide it into two halves. Whereas array R consists of 3 elements so we will also divide it into two parts where one will have more elements than the other.

Merge Sort picture 13

Now we will try to sort the individual sub arrays of L and merge them back in L. Likewise, we will sort the individual sub arrays of R and merge them back in R. Now these sub arrays can also be further divided into arrays consisting of single elements. This way we are creating a recursive pattern to solve the problem. Once we sort the individual sub arrays we will be able to merge them back to the original array. This reduction of a sub array will be continued till we are left with a single element in the sub array. The recursion will end at this point.

Merge Sort picture 14

A list with only one element is always sorted. Thus, now at this stage we will start merging the last sub arrays.

The sub array 4,1 after merging will be 1,4

Merge Sort picture 15

The subarray 5,2 after merging will be 2,5.

Merge Sort picture 16

At this stage, we can merge 1,4 and 2,5 as 1,2,4,5 in array L as shown below. Array L is now sorted.

Merge Sort picture 17

Lets move to the next single element subarrays and merge them back. The subarray 7,3 after merging will be 3,7 whereas 6 will simply be merged as it is.

Merge Sort picture 18

At this stage, we can merge 3,7 and 6 as 3,6,7 in array R as shown below. Array R is now sorted.

Merge Sort picture 19

Now these two sorted sub arrays L and R can be merged back to the original array X. Array X is now sorted.

Merge Sort picture 20

Pseudocode for Merge Sort

Let us show you the pseudocode for how we sorted array X using merge sort algorithm.

MergeSort(X)
{
  n=length(X)
  if (n<2) return
  middle=n/2
  L= array of size(middle)
  R= array of size(n-middle)
  for i=0 to (middle-1)
  L[i]=X[i]
  for i=middle to (n-1)
  R[i-middle]=X[i]
  MergeSort(L)
  MergeSort(R)
  Merge(L,R,X)
}

The MergeSort() function takes in a single argument that will be the array X. Inside the function, we will define a variable called ‘n’ that will store the number of elements in the array X. Then we will create a condition to divide the array into subarrays if ‘n’ is greater than 1. However, if ‘n’ is less than 2 then we will return. This is because this suggests that the array has only one element and is therefore sorted. Otherwise, we will find the middle position in the array and divide it accordingly. The array will therefore be divided into two parts. The first sub array will be of size middle and the second sub array will be of size (n-middle).

 middle=n/2
 L= array of size(middle)
 R= array of size(n-middle)

Next, we will run a for loop from i=0 till (mid-1) to fill the sub array L with elements till middle.

for i=0 to (middle-1)
  L[i]=X[i]

Likewise, we will run another for loop from i=middle to (n-1) to fill the remaining elements in the array X to the sub array R.

for i=middle to (n-1)
  R[i-middle]=X[i]

At this stage the left and right subarrays have been created and filled with elements from array X. Now, we will make a recursive call to sort the left sub array and the right sub array.

  MergeSort(L)
  MergeSort(R)

After both of the sub arrays L and R have been sorted, we will call Merge() function which we had previously looked upon in detail. This function will merge the sorted left and right sub arrays back to the original array X.

Merge(L,R,X)

Demonstrating Merge Sort Pseudocode using example array

Let us show you what happens to the our array of unsorted integers when this MergeSort() function is called. We will use the same example array that we have been using previously to understand the different concepts.

Merge Sort picture 1

We have passed this array X to the MergeSort() function. Now first the number of elements in the array will be calculated. In our case ‘n’ is 7. As it is greater than 2 hence we will proceed further. We will be creating two sub arrays L and R. These will be filled up with elements from array X. Now we will make a recursive call where the function is calling itself. First the merge sort function will execute on the left sub array of 4 elements: 4,1,5,2. We will again go to the beginning of the function and find the number of elements for this particular array. As they are greater than 2 hence we will move forward.

Merge Sort picture 21

We will again create further left and right sub arrays. There will be another recursive call. In that case the second MergeSort() function will get paused. The recursive calls will go on until we are left with a single element in the sub array. Now the array with elements 4,1 will be further split into sub arrays 4 and 1. The MergeSort() function will return and the Merge() function will be called.

Merge Sort pic 22

The control will return back to 4,1,5,2. This will call the second MergeSort() function. It will first make a call for this sub array with just one element and once this is done, it will make another recursive call. Then we will call the Merge() function for 5,2.

Merge Sort pic 23

Now control will go back to 4,1,5,2 and Merge will be called.

Merge Sort pic 24

After 1,2,4,5 will finish, the control will return to the original array. Now another recursive call will be made. This time to the second MergeSort() with R as an argument inside it. For the sub array R consisting of 7,3,6 we will have a recursive call passing 7,3 that will again cause a recursive call with just one element 7. Then we will have a call to 3 which will return.

Merge Sort pic 25

Once 3,7 returns, we will have a call for 6. As it is a single element hence it will return.

Merge Sort pic 26

At this stage 3,7 and 6 will merge and form 3,6,7 in the sub array R. Now both the sub arrays L and R are sorted.

Merge Sort pic 27

When execution for 3,6,7 will finish we will call Merge on the original array X. This will merge the two sorted sub arrays to X.

Merge Sort pic 28

This is how we used Merge Sort Algorithm to sort the list of integers in increasing order of values.

Merge Sort Example Code in C

#include <stdio.h>

void merge(int arr[], int begin, int mid, int end) {

  int lenght_1 = mid - begin + 1;
  int length_2 = end - mid;

  int left_arr[lenght_1], right_arr[length_2];

  for (int i = 0; i < lenght_1; i++)
    left_arr[i] = arr[begin + i];
  for (int j = 0; j < length_2; j++)
    right_arr[j] = arr[mid + 1 + j];

  int i, j, k;
  i = 0;
  j = 0;
  k = begin;

  while (i < lenght_1 && j < length_2) {
    if (left_arr[i] <= right_arr[j]) {
      arr[k] = left_arr[i];
      i++;
    } else {
      arr[k] = right_arr[j];
      j++;
    }
    k++;
  }

  while (i < lenght_1) {
    arr[k] = left_arr[i];
    i++;
    k++;
  }

  while (j < length_2) {
    arr[k] = right_arr[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int begin, int end) {
  if (begin < end) {

    int mid = begin + (end - begin) / 2;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, begin, mid, end);
  }
}

void print_arr(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main() {
  int arr[] = {11, 2, 5, 7, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);

  printf("Original array\n");
  print_arr(arr, size);

  mergeSort(arr, 0, size - 1);

  printf("Sorted array\n");
  print_arr(arr, size);
}
Original array
11 2 5 7 9 1
Sorted array
1 2 5 7 9 11

Other sorting Algorithms:

Leave a Comment