# Merge Sort

Merge Sort is a “Divide and Conquer” algorithm which first divides an input array in two sub-arrays, then it calls itself for those two sub-arrays, orders them and finally merges them into the original array. Write a merge sort program to sort an integer array in ascending order.

Difficulty: Easy.

### Input

• One integer representing the length of the integer array.
• n integers with neighboring elements separated by a space representing the elements of the array.

### Output

One line containing n integers which are the sorted array in ascending order, also separated by spaces.

### Example

Input:

`5`

`2 0 -3 4 5`

Output:

`-3 0 2 4 5`

### Solution: C++

```#include<iostream>

using namespace std;

// merge the two ordered arrays b and c into the original array a
void merge(int a[], int l, int m, int r){
int n1 = m - l + 1; //size of array b
int n2 =  r - m; //size of array c

// create temp arrays of b and c
int B[n1], C[n2];

int i, j;
// copy arrays a and b into temp arrays B and C
for (i = 0; i < n1; i++)
B[i] = a[l + i];
for (j = 0; j < n2; j++)
C[j] = a[m + 1 + j];

// merge the temp arrays A and B back into array a in the right position
i = 0; // index of B
j = 0; // index of C
int idx = l; // index of the array a
while (i < n1 && j < n2){
if (B[i] <= C[j]){
a[idx] = B[i];
i++;
}
else{
a[idx] = C[j];
j++;
}
idx++;
}

// copy the remaining elements of B into a
while (i < n1) {
a[idx] = B[i];
i++;
idx++;
}

// copy the remaining elements of C into a
while (j < n2) {
a[idx] = C[j];
j++;
idx++;
}
}

void mergeSort(int a[], int l, int r){
if (l < r){
int m = l+(r-l)/2; //index to split the the array a in two parts
mergeSort(a, l, m); // sort the first part
mergeSort(a, m+1, r); // sort the second part
merge(a, l, m, r); //merge the ordered two sub-array into array a
}
}

int main(){
int size;
cin>>size;
int a[size];
for(int i=0; i<size; i++)
cin>>a[i];

mergeSort(a, 0, size - 1);

for (int i=0; i < size; i++)
cout<<a[i]<<" ";
}
```