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)