Home » Algorithms

Merge Sort Algorithm: What It is, Time Complexity, and C++ Implementation

Merge Sort Algorithm: In this tutorial, we will learn about merge sort, its algorithm, and its implementation using C++ program. By Ankit Sood Last updated : August 12, 2023

What is sorting?

Sorting allows us to process our data in a more organized and efficient way. It makes searching easy as it will now take less time to search for a specific value in a given sorted sequence with respect to a sequence which was initially unsorted.

In programming, there are any numbers of sorting algorithms, some of them are given below,

1. Bubble sort
2. Selection sort
3. Insertion sort
4. Merge sort
5. Quick sort
6. Randomized Quick sort (an optimized quick sort)

Problem with other sorting techniques Vs. Why to use merge sort?

But, the problem with such sorting algorithms like bubble sort, insertion sort, and the selection sort is they take a lot of time to sort.

For example, If we have to sort an array of 10 elements then any sorting algorithm can be opted but in case of an extensively high value of N that is the no. of elements of the array like if N=1000000 then in case the starting 3 sorting algorithms cannot be opted as the time they will take is proportional to (N*N) which in big O notation can be represented as O(N*N).

So today we will focus on a more optimized sorting algorithm that is (MERGE SORT).

Basically, both merge and quick sort are divide and conquer algorithms.

Merge Sort Algorithm

But today we'll be focusing on MERGE SORT and the main reason of casting light upon this sorting algorithm is it takes O(N*logN) time which is very efficient with respect to the O(N*N).

Merge Sort Algorithm is considered as one of the best sorting algorithms having a worst case and best case time complexity of O(N*Log(N)), this is the reason that generally we prefer to merge sort over quicksort as quick sort does have a worst-case time complexity of O(N*N).

Basic steps

In merge sort we follow just 3 simple steps to sort an array:

1. Divide the array into two parts
2. Recursively sort both the parts
3. Then, merge those two stored parts into one

Merge sort algorithm Implementation using C++

The below is the implementation of merge sort using C++ program:

#include <iostream>
using namespace std;

int temp[10000];

void mergearrays(int ar[], int s, int e)
{
    int mid = (s + e) / 2;
    int i, j;
    i = s;
    j = mid + 1;
    int x = s;
    
    while (i <= mid && j <= e) {
        if (ar[i] < ar[j]) {
            temp[x++] = ar[i];
            i++;
        }

        else {
            temp[x++] = ar[j];
            j++;
        }
    }

    while (i <= mid) {
        temp[x++] = ar[i];
        i++;
    }
    while (j <= e) {
        temp[x++] = ar[j];
        j++;
    }

    for (int i = s; i <= e; i++)
        ar[i] = temp[i];
}

void mergesort(int ar[], int s, int e)
{
    int mid = (s + e) / 2;
    ///base case
    if (s >= e)
        return;
    ///recursive case
    mergesort(ar, s, mid);
    mergesort(ar, mid + 1, e);
    mergearrays(ar, s, e);
}

int main()
{
    int n;

    cout << "Enter total number of elements: ";
    cin >> n;

    int ar[10000];
    cout << "The unsorted array is (Enter elements): " << endl;
    for (int i = 0; i < n; i++)
        cin >> ar[i];

    mergesort(ar, 0, n - 1);

    cout << "The sorted array is" << endl;
    for (int i = 0; i < n; i++)
        cout << ar[i] << " ";

    return 0;
}

The output of the above program will be:

Enter total number of elements: 7
The unsorted array is (Enter elements):
7 4 6 5 3 2 1
The sorted array is
1 2 3 4 5 6 7