_ash__

merge sort iterative

Oct 27th, 2020
832
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Gene template< class
  5. #define Rics printer& operator,
  6. Gene c> struct rge{c b, e;};
  7. Gene c> rge<c> range(c i, c j){ return {i, j};}
  8. struct printer{
  9.     ~printer(){cerr<<endl;}
  10.     Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
  11.     Rics(string x){cerr<<x;return *this;}
  12.     Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
  13.     Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
  14.     Gene c >Rics(rge<c> x){
  15.         *this,"["; for(auto it = x.b; it != x.e; ++it)
  16.             *this,(it==x.b?"":", "),*it; return *this,"]";}
  17. };
  18. #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
  19. #define dbg(x) "[",#x,": ",(x),"] "
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21. int my_rand(int l, int r) {
  22.     return uniform_int_distribution<int>(l, r) (rng);
  23. }
  24.  
  25. // merges v[l...m], v[m+1...r]
  26. void Merge(vector<int> &v, int l, int m, int r) {
  27.     int ptr_l = l, ptr_r = m+1;
  28.     vector<int> merged;
  29.     while(ptr_l <= m or ptr_r <= r) {
  30.         if(ptr_l > m) {
  31.             merged.push_back(v[ptr_r]);
  32.             ptr_r++;
  33.         }
  34.         else if(ptr_r > r or v[ptr_r] > v[ptr_l]) {
  35.             merged.push_back(v[ptr_l]);
  36.             ptr_l++;
  37.         }
  38.         else {
  39.             merged.push_back(v[ptr_r]);
  40.             ptr_r++;
  41.         }
  42.     }
  43.     for(int i = l, j = 0; i <= r; i++, j++) {
  44.         v[i] = merged[j];
  45.     }
  46. }
  47.  
  48. void Sort(vector<int> &v) {
  49.    int n = v.size();
  50.    for(int cur_size = 1; cur_size < n; cur_size *= 2) {
  51.         for(int left_start = 0; left_start < n; left_start += 2 * cur_size) {
  52.             int mid = min(left_start + cur_size - 1, n - 1);
  53.             if(mid == n-1) continue;
  54.             int right_end = min(left_start + 2 * cur_size - 1, n - 1);
  55.             Merge(v, left_start, mid, right_end);
  56.         }
  57.    }
  58. }
  59.  
  60. int main() {
  61. //    freopen("in.txt", "r", stdin);
  62.     ios::sync_with_stdio(0);
  63.     cin.tie(0);
  64.  
  65.     for(int itr = 1; itr <= 10000; itr++) {
  66.         int n = my_rand(1, 100);
  67.         vector<int> v(n);
  68.         for(int i = 0; i < n; i++) {
  69.             v[i] = my_rand(-100000, 100000);
  70.         }
  71.         vector<int> tmp_v = v;
  72.         sort(tmp_v.begin(), tmp_v.end());
  73.         Sort(v);
  74.         assert(v == tmp_v);
  75.     }
  76. }
  77.  
RAW Paste Data