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]<<" ";
}