Merge Sort(Adv Cmp Class)
#include<bits/stdc++.h> using namespace std; const int mx = 1e9+7; int tmp[mx]; int final[mx]; void merge_sort(int l, int r){ if(l>=r) return; int mid = (l+r)/2; merge_sort(l, mid); merge_sort(mid+1, r); for(int i = l, lo = l, hi = mid+1; i<= r; i++){ if(lo==mid+1){ tmp[i] = final[hi++]; } else if(hi==r){ tmp[i] = final[lo++]; } else if(final[lo]<final[hi]){ tmp[i] = final[lo++]; } else{ tmp[i] = final[hi++]; } } for(int i = l; i<=r; i++) final[i] = tmp[i]; } void solution(){ int n; cin>>n; vector<int> vct(n); for(int i = 0; i<n; i++){ cin>>vct[i]; } merge_sort(0, n-1); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif solution(); }
Leave a Comment