Merge Sort in Data Structure

Suppose you are the head of an examination center. 4000 students are appearing for the examination and you have 50 invigilators at your center. After examination, you collect the answer sheets in random order. Now you have to arrange the sheets in increasing order of their roll numbers.

Arranging 4000 sheets is a very active and time-consuming task for a single person. So you divide these four thousand sheets into 50 invigilators. Each invigilator gets 80 sheets. The invigilator can divide their sets into further 4 subsets of 20 sheets each and assign a person under them to sort each set.

Once each individual set is sorted the sets are combined again and again in a recursive way to get a fully sorted set of answer sheets. This process is highly efficient and very less time-consuming.

Merge Sort

The merge sort algorithm is based on the divide and conquer algorithm technique. Merge sort divides the array into two subarrays. It performs this step recursively, sorts them, and then combines them to get a final sorted array.

1. One of the most efficient sorting algorithms is merge sort.

2. Merge sort uses recursion to divide the array into subarrays and sort them.

Merge Sort Procedure

1.Divide Array into two sub-array of an equal number of elements.

2. Sort the two sub-arrays recursively. Repeat step 1 for dividing the array upto base case.

3. Combine the sub-arrays recursively to form a single final sorted array

Merge Sort Algorithm

Merge ( array, low, mid, high)
Step 1: set i = low , j = mid + 1, index = 0
Step 2: while (i <= mid) and (j<= high)
             if array[i] < array[j]
             temp[index] = array[i]
              i++
             else
             temp[index] = array[j]
             j++
             [end of if]
             index++
             [end of loop]
Step 3: if i > mid
             while j <= high
             temp[index] = array[j]
             index ++
             j++
             [end of loop]
             else
             while i <= mid
             temp[index] = array[i]
             index++
             i++
             [end of loop]
             [end of if]
Step 4: set k = 0
Step 5: while k < index
            array[k] = temp[k]
            k++
            [end of loop]
Step 6: END
merge_sort(array, low, high)
Step 1: if low < high
            mid = (low + high)/2
            call merge_sort (array, low, mid)
            call merge_sort (array, mid + 1, high)
            merge (array, low, mid, high)
            [end of if]
Step 2: END

Merge Sort Pseudocode

procedure mergesort( array )
   if ( n == 1 ) return a

   subarray1 = a[0] ... a[n/2]
   subarray2 = a[n/2+1] ... a[n]

   subarray1 = mergesort( subarray1 )
   subarray2 = mergesort( subarray2 )

   return merge( subarray1, subarray2 )
end procedure

procedure merge( subarray1, subarray2 )

   subarray3
   while ( subarray1 and subarray2 are not empty)
      if ( subarray1[0] > subarray2[0] )
         add subarray2[0] to the end of subarray3
         remove subarray2[0] from subarray2
      else
         add subarray1[0] to the end of subarray3
         remove subarray1[0] from subarray1
      end if
   end while
   
   while ( subarray1 is not empty )
      add subarray1[0] to the end of subarray3
      remove subarray1[0] from subarray1
   end while
   
   while ( subarray2 is not empty )
      add subarray2[0] to the end of subarray3
      remove subarray2[0] from subarray2
   end while
   
   return subarray3
  
end procedure

Working of Merge Sort

We can see in the above example that the order of elements with the same value ‘A’ does not change in the sorted array. Therefore we can say that merge sort is a stable algorithm.

Implementation of merge sort in C

#include <stdio.h>

void merge(int arr[], int l, int m, int h) 
{

  int sub1 = m - l + 1;
  int sub2 = h - m;
 Int i, j;
  int L[sub1], M[sub2];

  for (i = 0; i < sub1; i++)
    L[i] = arr[l + i];
  for ( j = 0; j < sub2; j++)
    M[j] = arr[m + 1 + j];

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

  while (i < sub1 && j < sub2) 
  {
    if (L[i] <= M[j])
    {
      arr[k] = L[i];
      i++;
    } else 
    {
      arr[k] = M[j];
      j++;
    }
    k++;
  }

  while (i < sub1) 
  {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < sub2) 
  {
    arr[k] = M[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int low, int high) 
{
  if (low < high) 
  {

    int mid = low + (high - low) / 2;

    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);

    merge(arr, low, mid, high);
  }
}

int main() 
{
  int array[] = {31, 67, 53, 9, 26, 17,92, 74, 81, 40};
  int size = sizeof(array) / sizeof(array[0]);

  mergeSort(array, 0, size - 1);

  printf("Sorted array: \n");
   for (int i = 0; i < size; i++)
    printf("%d ", array[i]);
  
}

Merge Sort implementation in C++

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int h) 
{

  int sub1 = m - l + 1;
  int sub2 = h - m;

  int L[sub1], M[sub2];

  for (int i = 0; i < sub1; i++)
    L[i] = arr[l + i];
  for (int j = 0; j < sub2; j++)
    M[j] = arr[m + 1 + j];

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

  while (i < sub1 && j < sub2) 
  {
    if (L[i] <= M[j])
    {
      arr[k] = L[i];
      i++;
    } else 
    {
      arr[k] = M[j];
      j++;
    }
    k++;
  }

  while (i < sub1) 
  {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < sub2) 
  {
    arr[k] = M[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int low, int high) 
{
  if (low < high) 
  {

    int mid = low + (high - low) / 2;

    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);

    merge(arr, low, mid, high);
  }
}
int main() 
{
  int array[] = {31, 67, 53, 9, 26, 17,92, 74, 81, 40};
  int size = sizeof(array) / sizeof(array[0]);

  mergeSort(array, 0, size - 1);

  cout << "Sorted array:" ;
   for (int i = 0; i < size; i++)
    cout << " " << array[i];
  
}

Jave Merge Sort Implementation

public class MergeSort 
{

  void merge(int arr[], int l, int m, int h) 
  {

    int sub1 = m - l + 1;
    int sub2 = h - m;

    int L[] = new int[sub1];
    int M[] = new int[sub2];

    for (int i = 0; i < sub1; i++)
      L[i] = arr[l + i];
    for (int j = 0; j < sub2; j++)
      M[j] = arr[m + 1 + j];

    int i,j,k;
    i=j=0;
    k=l;
   
    while (i < sub1 && j < sub2) 
    {
      if (L[i] <= M[j]) 
      {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = M[j];
        j++;
      }
      k++;
    }

    while (i < sub1) 
    {
      arr[k] = L[i];
      i++;
      k++;
    }

    while (j < sub2) {
      arr[k] = M[j];
      j++;
      k++;
    }
  }

  void mergeSort(int arr[], int low, int high) 
  {
    if (low < high) 
    {

      int mid = (low + high) / 2;

      mergeSort(arr, low, mid);
      mergeSort(arr, mid + 1, high);

      merge(arr, low, mid, high);
    }
  }


  public static void main(String args[]) 
  {
    int arr[] = { 31, 67, 53, 9, 26, 17,92, 74, 81, 40 };

    MergeSort ms = new MergeSort();
    ms.mergeSort(arr, 0, arr.length - 1);

    System.out.println("Sorted array:");
    for (int i = 0; i < arr.length; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }
}

Implementation of merge sort in Python

def mergeSort(array):
    if len(array) > 1:

        r = len(array)//2
        L = array[:r]
        M = array[r:]
        mergeSort(L)
        mergeSort(M)

        i = j = k = 0

        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i =i+ 1
            else:
                array[k] = M[j]
                j = j+ 1
            k =k+ 1

        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1

        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1



if __name__ == '__main__':
    array = [31, 67, 53, 9, 26, 17,92, 74, 81, 40]

    mergeSort(array)

    print("Sorted array: ")
    for i in range(len(array)):
        print(array[i], end=" ")

Complexity of Merge Sort

Applications of merge sort

Merge sort is suitable for non-contiguous data, for example, linked list. Merge sort implementation in linked lists yields efficient results.
External merge sort algorithm for sorting massive data on systems with less memory.
Count inversions in an array. It is the count of steps that we need to sort the array.

Disadvantages of merge sort

Merge sort is not efficient if the array is already sorted. It has the same time complexity for the best and worst-case
In the case of small datasets, it is slower than other sorting techniques.
It requires additional memory equivalent to the size of the dataset.

Conclusion

Merge sort is one of the most efficient sorting techniques used in the real world. It is best suitable for large datasets, but for small datasets, it is less efficient than other prominent sorting techniques. The divide and conquer approach is one of the most efficient algorithm techniques for approaching a problem. We also discussed the working and implementation of merge sort in different programming languages.