Merge Sort in Data Structure

Merge sort is a sorting algorithm based on the Divide and conquer strategy. It works by recursively dividing the array into two equal halves, then sort them and combine them. It takes a time of (n logn) in the worst case.

What is Merge Sort?

The merge sort algorithm is an implementation of the divide and conquer technique. Thus, it gets completed in three steps:

1. Divide: In this step, the array/list divides itself recursively into sub-arrays until the base case is reached.

2. Recursively solve: Here, the sub-arrays are sorted using recursion.

3. Combine: This step makes use of the merge( ) function to combine the sub-arrays into the final sorted array.

Algorithm for Merge Sort

Step 1: Find the middle index of the array.
Middle = 1 + (last – first)/2
Step 2: Divide the array from the middle.
Step 3: Call merge sort for the first half of the array
MergeSort(array, first, middle)
Step 4: Call merge sort for the second half of the array.
MergeSort(array, middle+1, last)
Step 5: Merge the two sorted halves into a single sorted array.

Follow TechVidvan on Google & Stay updated with latest technology trends

Pseudo-code for Merge Sort

Consider an array Arr which is being divided into two sub-arrays left and right. Let L1 = Number of elements in the left sub-array; and L2 = Number of elements in the right sub-array.

Let variable i point to the first index of the left sub-array and j point to the first index of the right sub-array. Then, the pseudo-code for the merge( ) function will be:

procedure merge(Arr[], lt, mid, rt):
    int L1 = mid - lt + 1
    int L2 = rt-mid
    int left[L1], right[L2]
    
    for i = 0 to L1:
        left[i] = Arr[lt + i]
    END for loop
    
    for j = 0 to L2:
        right[j] = Arr[mid+1+j]
    END for loop
    
    while(left and right hve elments):
        if(left[i] < right[j])
            Add left[i] to the end of Arr
        else
            Add right[i] to the end of Arr
    END while loop
    
END procedure    

procedure Merge_sort(Arr[]):
    l1 = Merge_sort(L1)
    l2 = Merge_sort(L2)
    return merge(l1, l2)
END procedure

Working of Merge Sort

Consider an array having the following elements: 1,6,3,2,7,5,8,4. We need to sort this array using merge sort.

Merge Sort Example

There is a total of 8 elements in the array. Thus, mid = 4. So we will first divide this array into two arrays of size 4 as shown:

Merge Sort Working

Next, we recursively divide these arrays into further halves. The half of 4 is 2. So, now we have 4 arrays of size 2 each.

Merge Sort Iterations

We will keep on dividing into further halves until we have reached an array length of size 1 as shown:

Iterations in merge Sort

After this, we have the combining step. We will compare each element with its consecutive elements and arrange them in a sorted manner.

Merge sort Working

In the next iteration, we will compare two arrays and sort them as shown:

Merge Sort Iterations

Finally, we will compare the elements of the two arrays each of size 4 and we will get our resultant sorted array as shown:

Merge Sort Output

Characteristics of Merge Sort

1. External sorting algorithm: Merge sort can be used when the data size is more than the RAM size. In such a case, whole data cannot come into RAM at once. Thus, data is loaded into the RAM in small chunks and the rest of the data resides in the secondary memory.

2. Non-inplace sorting algorithm: Merge sort is not an inplace sorting technique as its space complexity is O(n). Inplace or space-efficient algorithms are those whose space complexity is not more than O(logn).

Implementation of Merge Sort in C

#include <stdio.h>
#include <stdlib.h>

void Merge_sort(int[], int, int);
void merge(int[], int, int, int);
 void Display_array(int[], int);
int main()
{
    int array[] = {1,6,3,2,7,5,8,4};
    int arr_size = sizeof(array) / sizeof(arr[0]);
 
    printf("Given array is: \n");
    Display_array(array, arr_size);
    Merge_sort(array, 0, arr_size - 1);
    printf("\nSorted array is: \n");
    Display_array(array, arr_size);
    return 0;
}

void merge(int Arr[], int lt, int mid, int rt)
{
    int i, j, k;
    int L1 = mid - lt + 1;
    int L2 = rt - mid;
    int left[L1], right[L2];    //Creating temporary arrays, additional memory needed
    for (i = 0; i < L1; i++)
        left[i] = Arr[lt + i];
        
    for (j = 0; j < L2; j++)
        right[j] = Arr[mid + 1 + j];
    i = j = 0;
    k = 1;
    while (i < L1 && j < L2) {
        if (left[i] <= right[j]) {
            Arr[k] = left[i];
            i++;
        }
        else {
            Arr[k] = right[j];
            j++;
        }
        k++;
    }
 
    while (i < L1) 
        Arr[k++] = left[i++];
 
    while (j < L2) 
        Arr[k++] = right[j++];
}

void Merge_sort(int Arr[], int l, int r)
{
    if (l < r) {
        int mid = l + (r - l) / 2;
        Merge_sort(Arr, l, mid);
        Merge_sort(Arr, mid + 1, r);
        merge(Arr, l, mid, r);
    }
}

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

Implementation of Merge Sort in C++

#include <bits/stdc++.h>
using namespace std;

void merge(int[], int, int, int);
void Merge_sort(int[], int, int);
void Display_array(int[], int);

int main()
{
  int array[] = {1,6,3,2,7,5,8,4};
  auto arr_size = sizeof(array) / sizeof(arr[0]);

  cout << "Given array is: \n";
  Display_array(array, arr_size);
  Merge_sort(array, 0, arr_size - 1);

  cout << "\nThe sorted array is: \n";
  Display_array(array, arr_size);
  return 0;
}

void merge(int Arr[], int lt, int mid, int rt)
{
  L1 = mid - lt + 1;
  L2 = rt - mid;
    int i, j, k;
  auto *left = new int[L1],
    *rightArray = new int[L2];
    
  for (int i = 0; i < L1; i++)
    left[i] = Arr[lt + i];
  for (int j = 0; j < L2; j++)
    right[j] = Arr[mid + 1 + j];
    i = j = 0;
    k = 1;

while (i < L1 && j < L2) {
        if (left[i] <= right[j]) {
            Arr[k] = left[i];
            i++;
        }
        else {
            Arr[k] = right[j];
            j++;
        }
        k++;
    }
 
    while (i < L1) 
        Arr[k++] = left[i++];
 
    while (j < L2) 
        Arr[k++] = right[j++];

}

void Merge_sort(int Arr[], int l, int r)
{
    if (l < r) {
        int mid = l + (r - l) / 2;
        Merge_sort(Arr, l, mid);
        Merge_sort(Arr, mid + 1, r);
        merge(Arr, l, mid, r);
    }
}


void Display_array(int a[], int size)
{
  for (int i = 0; i < size; i++)
    cout << a[i] << " ";
}

Merge Sort Implementation in Java

class MergeSort
{
  void merge(int Arr[], int lt, int mid, int rt)
  {
    int L1 = mid - lt + 1;
    int L2 = rt - mid;
    int left[] = new int[L1];
    int right[] = new int[L2];

    for (int i = 0; i < L1; i++)
      left[i] = Arr[lt + i];
    for (int j = 0; j < L2; j++)
      right[j] = Arr[mid + 1 + j];
    int i = 0, j = 0;
    int k = l;
    while (i < L1 && j < L2) {
      if (left[i] <= right[j]) {
        Arr[k] = left[i];
        i++;
      }
      else {
        Arr[k] = right[j];
        j++;
      }
      k++;
    }

    while (i < L1) 
      Arr[k++] = left[i++];
  
    while (j < L2) 
      Arr[k++] = right[j++];
  }

  void Merge_sort(int Arr[], int l, int r)
  {
    if (l < r) {
      int mid =l+ (r-l)/2;
      Merge_sort(Arr, l, mid);
      Merge_sort(Arr, mid + 1, r);
      merge(Arr, l, mid, r);
    }
  }

  static void Display_array(int a[])
  {
    int n = a.length;
    for (int i = 0; i < n; ++i)
      System.out.print(a[i] + " ");
    System.out.println();
  }

  public static void main(String args[])
  {
    int array[] = {1,6,3,2,7,5,8,4};
    System.out.println("Given array is: ");
    Display_array(array);
    MergeSort ob = new MergeSort();
    ob.Merge_sort(array, 0, array.length - 1);
    System.out.println("\nSorted array is: ");
    Display_array(array);
  }
}

Implementation of Merge Sort in Python

def Merge_sort(Arr):
  if len(Arr) > 1:
    mid = len(Arr)//2
    left = Arr[:mid]
    right = Arr[mid:]
    Merge_sort(left)
    Merge_sort(right)

    i = j = k = 0
    while i < len(left) and j < len(right):
      if len[i] < right[j]:
        Arr[k] = left[i]
        i += 1
      else:
        Arr[k] = right[j]
        j += 1
      k += 1

    while i < len(left):
      Arr[k] = left[i]
      i += 1
      k += 1

    while j < len(right):
      Arr[k] = right[j]
      j += 1
      k += 1

def Display_list(a):
  for i in range(len(a)):
    print(a[i], end=" ")
  print()

if __name__ == '__main__':
  list = [1,6,3,2,7,5,8,4]
  print("Given array is: ", end="\n")
  Display_list(list)
  Merge_sort(list)
  print("Sorted array is: ", end="\n")
  Display_list(list)

Complexity of Merge Sort

ScenarioTime complexity
Worst caseO(n logn)
Average caseO(n logn)
Best caseO(n logn)

The space complexity of merge sort is O(n).

Applications of Merge Sort

1. To sort linked lists in O(n logn) time: In the case of a linked list, we can insert the element in the middle or anywhere in between the linked list with time complexity of O(1). If we use merge sort to sort such a linked list, we can do so with the space complexity of O(1). Also, we cannot do random access in a linked list and merge sort also does not work well in case of random access. Thus, merge sort is the best algorithm to sort a linked list with the complexity of O(n logn).

2. Inversion count problem: Merge sort helps to solve this problem by telling the number of inversion pairs in an unsorted array. The inversion count problem tells how many pairs need to be swapped in order to get a sorted array. Merge sort works best for solving this problem.

3. External sorting: Merge sort is an external sorting technique. Thus, if we have data of 1GB but the available RAM size is 500MB, then we will use merge sort.

Drawbacks of Merge Sort

  • Merge sort is not a space-efficient algorithm. It makes use of an extra O(n) space.
  • In the case of smaller input size, merge sort works slower in comparison to other sorting techniques.
  • If the data is already sorted, merge sort will be a very expensive algorithm in terms of time and space. This is because it will still traverse the whole array and perform all the operations.

Conclusion

Merge sort is one of the most widely used algorithms in data structures. Although it is not a space-efficient algorithm, its time complexity is of the order O(n logn) which is better than most of the sorting algorithms. Whenever we have an input size larger than the RAM size, we use merge sort. Thus, merge sort is very well suited for larger datasets.

In this article, we have studied what is merge sort, how it works, its applications, drawbacks as well as its implementation in various programming languages.

Did we exceed your expectations?
If Yes, share your valuable feedback on Google | Facebook


Leave a Reply

Your email address will not be published. Required fields are marked *