Envío 2517

Código

#include<iostream>
#include<vector>

using namespace std;

void merge(vector<int> &A,int p, int q, int r){
   int n1 =  q-p+1;
   int n2 = r-q;
   vector<int>L(n1,0);
   vector<int>M(n2,0);
   for(int i=0;i<n1;i++){
       L[i] = A[p+i];
   }
   for(int j=0;j<n2;j++){
       M[j] = A[q+1+j];
   }

   int i=0,j=0,k=p;
   while(i<n1 && j<n2){
       if(L[i]<=M[j]){
           A[k] = L[i];
           i++;
       }
       else{
           A[k]= M[j];
           j++;
       }
       k++;
   }

   while(i<n1){
       A[k]=L[i];
       i++;
       k++;
   }
   while(j<n2){
       A[k]=M[j];
       j++;
       k++;
   }
}


void mergeSort(vector<int> &A, int p, int r){
    if(p<r){
        int m  = p+(r-p)/2;
        mergeSort(A,p,m);
        mergeSort(A,m+1,r);
        merge(A,p,m,r);
    }
}

int main(){
    int n;
    cin>>n;
    vector<int> vals(n);
    for(auto &val: vals){
        cin>>val;
    }
    mergeSort(vals,0,vals.size()-1);
    for(int val:vals){
        cout<<val<<" ";
    }
    cout<<"\n";
    return 0;
}