ulvis.paste.net

Paste Search Dynamic
Recent pastes
kars_sort
  1. #include <bits/stdc++.h>
  2.  
  3. template <typename It>
  4. inline It
  5. upper_sorted_bound (It first, It last)
  6. {
  7.         if(first == last) return last;
  8.         auto second = first;
  9.         for(++second; second != last && *first <= *second; ++first, ++second);
  10.         return second;
  11. }
  12.  
  13. template <typename It>
  14. inline void
  15. kars_sort (It first, It last)
  16. {
  17.         if(std::distance(first, last) <= 1) return;
  18.        
  19.         using seg_t = std::vector <std::pair <It, It> >;
  20.         std::vector<seg_t> segs(2);
  21.         auto& seg = segs[0];
  22.         for(auto f = first, l = last; f != l;) {
  23.                 auto s = upper_sorted_bound (f, l);
  24.                 seg.emplace_back(f, s);
  25.                 f = s;
  26.         }
  27.        
  28.         for(; seg.size() != 1;) {
  29.                 auto& newseg = segs[1];
  30.                 newseg.clear();
  31.                 for(size_t i = 0; i < seg.size(); i +=2) {
  32.                         if(i + 1 == seg.size()) {
  33.                                 newseg.emplace_back(seg[i]);
  34.                         }
  35.                         else {
  36.                                 std::inplace_merge(seg[i].first, seg[i].second, seg[i+1].second);
  37.                                 newseg.emplace_back(seg[i].first, seg[i+1].second);
  38.                         }
  39.                 }
  40.                 seg.swap(newseg);
  41.         }
  42. }
  43.  
  44. using namespace std;
  45. int main () {
  46.         vector<int> a {1, 2, 3, 0, 2, 2, 4, -1, 2, 0, -6};
  47.         auto aa = a; sort(aa.begin(), aa.end());
  48.        
  49.        
  50.         for(auto x : a) cout << x << " ";
  51.         cout << endl;
  52.        
  53.         kars_sort(a.begin(), a.end());
  54.        
  55.         for(auto x : a) cout << x << " ";
  56.         cout << endl;
  57.        
  58.         for(auto x : aa) cout << x << " ";
  59.         cout << endl;
  60. }
Parsed in 0.011 seconds