inhuman_Arif

Merge sort

Oct 20th, 2021
677
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. void merge(int arr[],int left, int mid, int right)
  6. {
  7.     int l_size = (mid-left)+1;
  8.     int r_size = right-mid;
  9.  
  10.     int l_arr[l_size],r_arr[r_size];
  11.     for(int i=0;i<l_size;i++)
  12.         l_arr[i] = arr[left+i];
  13.     for(int i=0;i<r_size;i++)
  14.         r_arr[i] = arr[mid+1+i];
  15.  
  16.     int i=0,j=0,k=left;
  17.     while(i<l_size and j<r_size)
  18.     {
  19.         if(l_arr[i]<=r_arr[j])
  20.         {
  21.             arr[k] = l_arr[i];
  22.             i++;
  23.         }
  24.         else
  25.         {
  26.             arr[k] = r_arr[j];
  27.             j++;
  28.         }
  29.         k++;
  30.     }
  31.     while(i<l_size)
  32.     {
  33.         arr[k] = l_arr[i];
  34.         i++;
  35.         k++;
  36.     }
  37.     while(j<r_size)
  38.     {
  39.         arr[k] = r_arr[j];
  40.         j++;
  41.         k++;
  42.     }
  43. }
  44.  
  45. void mergesort(int arr[],int left,int right)
  46. {
  47.     if(left>=right)
  48.         return;
  49.     int mid = left+(right-left)/2;
  50.     mergesort(arr,left,mid);
  51.     mergesort(arr,mid+1,right);
  52.     merge(arr,left,mid,right);
  53. }
  54.  
  55. int main()
  56. {
  57.     #ifndef ONLINE_JUDGE
  58.         freopen("input.txt", "r", stdin);
  59.         freopen("output.txt", "w", stdout);
  60.     #endif
  61.  
  62.     int n;
  63.     cin >> n;
  64.     int arr[n];
  65.     for(int i=0;i<n;i++)
  66.         cin >> arr[i];
  67.        
  68.     mergesort(arr,0,n-1);
  69.  
  70.     for(int i=0;i<n;i++)
  71.         cout << arr[i] << ' ';
  72.    
  73.     return 0;
  74. }
RAW Paste Data