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)