Q:

# Merge Sort in C++ with Example

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
```