farhin_khaled

Merge Sort

Oct 20th, 2021 (edited)
715
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ull unsigned long long int
  4. #define pb push_back
  5. #define mp make_pair
  6. #define in insert
  7. #define f first
  8. #define sc second
  9. #define M 1000000
  10. #define MAX 1000010
  11. using namespace std;
  12.  
  13. void merge(int lb,int ub,int a[],int mid,int n)
  14. {
  15.   int i = lb,j = mid+1,k = lb,b[n];
  16.   while(i<=mid && j<=ub)
  17.   {
  18.     if(a[i]<=a[j]){b[k] = a[i];i++;k++;}
  19.     else {b[k] = a[j];j++;k++;}
  20.   }
  21.   if(i>mid)
  22.   {
  23.     while(j<=ub){b[k] = a[j];k++;j++;}
  24.   }
  25.   else
  26.   {
  27.     while(i<=mid){b[k] = a[i];i++;k++;}
  28.   }
  29.  
  30.   for(i=lb;i<=ub;i++) a[i] = b[i];
  31. }
  32. void mergeSort(int lb,int ub,int a[],int n)
  33. {
  34.   int mid;
  35.   if(lb<ub)
  36.   {
  37.     mid = (lb+ub)/2;
  38.     mergeSort(lb,mid,a,n);
  39.     mergeSort(mid+1,ub,a,n);
  40.     merge(lb,ub,a,mid,n);
  41.   }
  42. }
  43.  
  44. int main()
  45. {
  46.   int n;
  47.   cin >> n;
  48.   int a[n];
  49.   for(int i=0;i<n;i++) cin >> a[i];
  50.   cout << "Before sorting:" << endl;
  51.   for(int i=0;i<n;i++) cout << a[i] << " ";
  52.   cout << endl << endl;
  53.   mergeSort(0,n-1,a,n);
  54.   cout << "After sorting:" << endl;
  55.   for(int i=0;i<n;i++) cout << a[i] << " ";
  56.  
  57.   return 0;
  58. }
  59.  
RAW Paste Data