# Write a program to implement merge sort algorithm.

Given an integer array, we need to sort in ascending order using merge sort algorithm.

Example:

``````input:arr[]={1,5,3,2}
output:1,2,3,5``````

Logic:

``````Step 1- find the midpoint of array.
step 2-divide the array into multiple subpart.
step 3-sort the subpart
step 4-then merge all the subpart.
step 5- finally u got your sorted array.``````

Code-

```#include<iostream>
using namespace std;
void swapping(int &a, int &b) {
int temp;
temp = a;
a = b;
b = temp;
}
void merge(int *a, int l, int m, int r) {
int i, j, k;
int n1, n2;
n1 = m-l+1;
n2 = r-m;
int a1[n1];
int a2[n2];
for(i = 0; i<n1; i++)
{
a1[i] = a[l+i];
}
for(j = 0; j<n2; j++)
{
a2[j] = a[m+1+j];
}
i = 0; j = 0; k = l;
while(i < n1 && j<n2)
{
if(a1[i] <= a2[j])
{
a[k] = a1[i];
i++;
}
else{
a[k] = a2[j];
j++;
}
k++;
}
while(i<n1)
{
a[k] = a1[i];
i++; k++;
}
while(j<n2)
{
a[k] = a2[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int mid;
if(l < r) {
mid = l+(r-l)/2;
mergeSort(array, l, mid);
mergeSort(array, mid+1, r);
merge(array, l, mid, r);
}
}
int main() {

int array[]={4,5,3,2,1};
int n = sizeof(array)/sizeof(array[0]);
mergeSort(array, 0, n-1);
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}```

Output:

`1 2 3 4 5`

Time complexity:0(NLOGN)

Space Complexity:O(N)

Scroll to Top