Merge Sort Algorithm in Data Structures

In the previous article, we learned about Quick Sort Algorithm, In this article, we will learn about the Merge sort algorithm in Data Structures.

507

The Merge Sort algorithm is one of the most popular algorithms for sorting an array. Merge Sort algorithm is based on the principle of divide and conquer.

What is merge sort algorithm in data structures

This algorithm is a bit complex. Here, we divide the unsorted array into two halves. Again, the two halves are divided into two halves. This process continues till the smallest blocks are received and no further division is possible.

Then, we merge these blocks in such a way that the resulting blocks are sorted among themselves. This is done till the array of the initial size is received. On completion of this, we will see that the array is sorted.

We will now understand the codes for this algorithm –

#include <iostream>

using namespace std;

void merge(int arr[], int p, int q, int r) {

  int n1 = q - p + 1;

  int n2 = r - q;

  int L[n1], M[n2];

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

    L[i] = arr[p + i];

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

    M[j] = arr[q + 1 + j];

  int i, j, k;

  i = 0;

  j = 0;

  k = p;

  while (i < n1 && j < n2) {

    if (L[i] <= M[j]) {

      arr[k] = L[i];

      i++;

    } else {

      arr[k] = M[j];

      j++;

    }

    k++;

  }

  while (i < n1) {

    arr[k] = L[i];

    i++;

    k++;

  }

  while (j < n2) {

    arr[k] = M[j];

    j++;

    k++;

  }

}

void mergeSort(int arr[], int l, int r) {

  if (l < r) {

    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);

    mergeSort(arr, m + 1, r);

    merge(arr, l, m, r);

  }

}

void printArray(int arr[], int size) {

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

    cout << arr[i] << " ";

  cout << endl;

}

int main() {

  int arr[] = {5,18,3,23,2,6};

  int size = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, 0, size - 1);

  cout << "Sorted array: \n";

  printArray(arr, size);

  return 0;

}

Output –

2,3,5,6,18,23

Time Complexity of the Merge sort algorithm –

For this algorithm, the time complexity for all three cases is the same.

Best Time Complexity – O(n*log n)

Average Time Complexity – O(n*log n)

Worst Time Complexity – O(n*log n)

Space Complexity of the Merge sort algorithm–

The space complexity for this algorithm is O(n). This means that this algorithm takes up a lot of space and may slow down operations for the last data sets.

So, in this article, we learned about the Merge Sort Algorithm. This algorithm is also used at –

  • Inversion count problem
  • External sorting
  • E-commerce applications.

Fundamentals of Data Structures and Algorithms MCQ Test

Previous QuizQuick Sort Algorithm in Data Structures
Next QuizCatergorizing laws – Public & Private Law By Dr. Shilpi Agarwal, Sandip University

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.