Merge Sort in C++ with Example

Learn: Merge Sort in C++ with Example, Algorithm. Merge sort is the sorting technique of Data Structure, here we will learn Merge sort implementation using C++.
Submitted by Shubham Singh Rajawat, on June 09, 2017

Merge sort follows the approach of Divide and Conquer.

Divide means breaking a problem into many small sub problems.

Conquer means solving those small sub problems recursively and then recombine them to create a solution of the original problem.

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.

Program for Merge Sort in C++

#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