Merge Sort in C++ with Example

Merge sort algorithm in C++ with example: In this tutorial, we will learn about the merge sort algorithm and the implementation of merge sort using the C++ program. By Shubham Singh Rajawat Last updated : August 06, 2023

Merge sort algorithm

The merge sort (or, mergesort) algorithm is an efficient, general-purpose, and comparison-based sorting algorithm. It is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output.

Merge sort follows the approach of Divide and Conquer. Where, Divide means breaking a problem into many small sub-problems, and Conquer means solving those small sub-problems recursively and then recombining them to create a solution to the original problem.

C++ program to implement merge sort algorithm

#include <iostream>

using namespace std;

// It merges two arrays
void Merge(int A[], int p, int q, int r)
{
    // n1 is the size of L[]
    int n1 = q - p + 1, i, j, k;

    // n2 is the sixe of R[]
    int n2 = r - q;

    int L[n1], R[n2];

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

    {
        L[i] = A[p + i];
    }

    for (j = 0; j < n2; j++) {
        R[j] = A[q + j + 1];
    }

    i = 0, j = 0;

    for (k = p; i < n1 && j < n2; k++) {
        if (L[i] < R[j]) {
            A[k] = L[i++];
        }
        else {
            A[k] = R[j++];
        }
    }

    /*
        If L[] has more elements than R[] then it will 
        put all the reamining elements of L[] into A[]
    */
    while (i < n1) {
        A[k++] = L[i++];
    }

    // If R[] has more elements than L[] then it will put all
    // the reamining elements of R[] into A[]
    while (j < n2) {
        A[k++] = R[j++];
    }
}

// It will will divide the array and sort
// them while merging them
void MergeSort(int A[], int p, int r)
{
    int q;

    if (p < r) {
        // q is the middle element to divide the array
        q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}

int main()
{
    // A_Size size of A[]
    int A_Size;

    cout << "Enter number of elements : ";

    cin >> A_Size;

    int A[A_Size];

    cout << "Enter the array elements : ";

    for (int i = 0; i < A_Size; i++) {
        cin >> A[i];
    }

    MergeSort(A, 0, A_Size - 1);

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

    cout << endl;

    return 0;
}

Output

First Run:
Enter number of elements : 5
Enter the array elements : 10 30 12 56 60
10 12 30 56 60

Second Run:
Enter number of elements : 10
Enter the array elements : 10 20 50 60 77 88 34 43 1 45
1 10 20 34 43 45 50 60 77 88

Explanation

The method MergeSort() breaks the array into equal parts until every element get separated and then the method Merge() recombines them while sorting them every time it joins two arrays it joins them in a sorted way so that we get a final sorted array.