Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.5 kB
4
Indexable
Never
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
using namespace std ;
const int maxn = 1e5+7;
int b[maxn] , d[maxn] , ans;


void merge(int l , int mid , int r){
    int p1 = l , p2 = mid , k = l;
    while(p1 != mid+1 && p2 != r+1){
        if(p2 == r && p1 != mid){
            d[k] = b[p1];
           // cout << d[k] << ' ' ;
            p1++;
   
        }
        else if (p1 == mid && p2 != r){
            d[k] = b[p2];
            p2++;
    
        }
        else if(b[p1] < b[p2]){
           //cout << b[p1] << ' ' << b[p2] << '\n';
            d[k] = b[p1];
            p1++;
 
        }
        else if(b[p2] <= b[p1]){
           // cout << '*' << b[p2] << ' ' << b[p1] << '\n';
            d[k] = b[p2];
            p2++;
      //      ans++;
        }

    k++;
    }
    for(int i = l ; i <= r ; i++){
            b[i] = d[i];
    }
}
void sorting(int l , int r){
   // cout << "ha";
    int mid = (l+r) >> 1;
    if(l >= mid) return ;
    if(mid >= r) return ;
    //cout << l << ' ' << mid << ' ';
    //cout << mid << ' ' << r << '\n';
    sorting(l , mid);
    sorting(mid , r);
    merge(l , mid , r);
    
}
int main(){
    ios;
    int a , n;
    cin >> a;
    for(int i = 0 ; i < a ;i++){
        cin >> b[i];
    }
   // cout << "ha";
    sorting(0 , a);
    for(int i = 0 ; i < a ; i++){
     cout << d[i] << ' ';
    }
    //cout << ans;
    return 0;
}