Advertisement
konchin_shih

merge sort

Jun 1st, 2021
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. template<typename T> using V=vector<T>;
  5. void merge_sort(V<int>& v,int l,int r){
  6.     if(r-l<2) return;
  7.     int m=(l+r)>>1;
  8.     merge_sort(v,l,m);
  9.     merge_sort(v,m,r);
  10.     static V<int> arr;//暫存用
  11.     arr.resize(v.size());
  12.     copy(v.begin()+l,v.begin()+r,arr.begin()+l);
  13.     int lptr=l,rptr=m,ptr=l;
  14.     while(lptr<m&&rptr<r)
  15.         if(arr[lptr]<=arr[rptr])
  16.             v[ptr++]=arr[lptr++];
  17.         else
  18.             v[ptr++]=arr[rptr++];
  19.     while(lptr<m)
  20.         v[ptr++]=arr[lptr++];
  21.     while(rptr<r)
  22.         v[ptr++]=arr[rptr++];
  23. }
  24.  
  25. int main(){
  26.     V<int> v{1,5,4,2,0,3,6,7,9,8};
  27.     merge_sort(v,0,v.size());
  28.     for(const auto& i:v)
  29.         cout<<i<<' ';
  30.     cout<<endl;
  31.     return 0;
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement