Merge sort in c++ (A Divide and Conquer algorithm)

In this tutorial, we will learn another technique of sorting i.e Merge sort. First, we will learn what is the merge sort and what is how does it uses the divide and conquer algorithm?

Merge sort is a divide and conquer algorithm. We always need sorting with effective complexity. A Divide and Conquer algorithm works on breaking down the problem into sub-problems of the same type, until they become simple enough to be solved independently.

 

ALGORITHM OF MERGE SORT

void mergesort(int a[], int low, int high)

Merge sort uses the following algorithm. Let the array be {12,23,4,3,56,78,9,10}

1. 1. First, calculate the middle index of the array, which divides the array into two halves.
   2. Call the mergesort for the first half.mergesort(a, low, middle);
   3. Call the mergesort for the second half.mergesort(a, middle + 1, high);
   4. Merge the two arrays in steps 2 and 3 with the help of the merge function.merge(a, low, middle, high);

From the following diagram, we can see how the array is divided into two halves till the size becomes 1 and then recursively merged into one array. Once the size becomes 1, the array starts to merge until we get back the whole array.

The numbers in the following figure represent the sequence of calling:

If we look at the diagram, we can figure out how the whole array is divided into two halves until the size becomes 1. Once the size becomes 1, it merges back till we get the whole array and the subarrays are also sorted.

Time complexity of merge sort

Time complexity can be defined by the following recurrence relation.

T(n)=2T(n/2)+theta(n) (As it divides the problem in two problems of size n/2 and merge them in o(n)).

The above can be solved using the recurrence tree method or second case of the master method. After solving, we get theta(nlogn).

Auxiliary space of merge sort

o(n)

Also, refer to these sorting techniques:

• Bubble sort
• Radix sort
• Dijkstra’s shortest path algorithm in C++

Code to perform merge sort in C++

#include <bits/stdc++.h>

using namespace std;

void mergeofarrays(int a[], int low, int mid, int high) {
  int i = low, j = mid + 1, index = low, temp[100], k;

  while ((i <= mid) && (j <= high)) {
    if (a[i] < a[j]) {
      temp[index] = a[i];
      i++;
    } else {
      temp[index] = a[j];
      j++;
    }
    index++;
  }

  //copy the remaining elements of right array
  if (i > mid) {
    while (j <= high) {
      temp[index] = a[j];
      j++;
      index++;
    }
  } else //remaining elements of left array
  {
    while (i <= mid) {
      temp[index] = a[i];
      i++;
      index++;
    }
  }

  for (k = low; k < index; k++) //copying into original array
  {
    a[k] = temp[k];
  }

}

void mergesort(int a[], int low, int high) {
  if (low < high) {
    int middle = (low + high) / 2; //calculating middle index of array to divide it in two halves

    mergesort(a, low, middle); //sorting first half
    mergesort(a, middle + 1, high); //sorting second half

    mergeofarrays(a, low, middle, high); //merging 2 sorted halves
  }
}

int main() {
  int n = 7;
  int a[100] = {54,34,23,10,98,2,3};
  mergesort(a, 0, 6);

  for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
  }
}

output:

2 3 10 23 34 54 98