Merge Sort in C++ with Example

belongs to collection: Data Structure programs using C and C++ (Sorting Programs)

mahmoud2506

Save to bookmark

2022-05-09

170

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.

C++ programming, exam questions, C++ programming exam-questions,

All Answers

mahmoud2506

2022-05-09

need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)