Advertisement
Guest User

Untitled

a guest
Mar 18th, 2019
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std ;
  4.  
  5. deque<int> a ;
  6.  
  7. deque<int> mergeSort(deque<int> x){
  8.     deque<int> ret ;
  9.  
  10.     if(x.size() == 1) return x ;
  11.     deque<int> l , r ;
  12.  
  13.     int low = 0 , hi = x.size() ;
  14.     int mid = low + hi >> 1 ;
  15.  
  16.     for(int i = 0 ; i < mid ; i ++) l.push_back(x[i]);
  17.     for(int i = mid ; i < hi ; i ++) r.push_back(x[i]);
  18.  
  19.     l = mergeSort(l);
  20.     r = mergeSort(r);
  21.  
  22.  
  23.  
  24.     while(!l.empty() && !r.empty()){
  25.         if(l.front() <= r.front()){
  26.             ret.push_back(l.front());
  27.             l.pop_front();
  28.         }
  29.         else{
  30.             ret.push_back(r.front());
  31.             r.pop_front();
  32.         }
  33.     }
  34.     while(!l.empty()){
  35.         ret.push_back(l.front());
  36.         l.pop_front();
  37.     }
  38.     while(!r.empty()){
  39.         ret.push_back(r.front());
  40.         r.pop_front();
  41.     }
  42.  
  43.     return ret ;
  44.  
  45.  
  46. }
  47.  
  48. int main(){
  49.     int n ;
  50.  
  51.     int x;
  52.  
  53.     for(int i = 0 ; scanf("%d",&x)!= EOF ; i ++){
  54.  
  55.  
  56.         a.push_back(x);
  57.     }
  58.  
  59.     a = mergeSort(a);
  60.  
  61.     for(int i =0 ; i < a.size() ; i ++)
  62.         printf("%d ",a[i]);
  63.  
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement