Envío 4453

Código

#include <bits/stdc++.h>
using namespace std;

void merge(vector<int> &arr, int l_, int m, int r){
	vector<int> left(m-l_+1), rigth(r-m);

	for(int i=l_, j=0; i<=m; ++i, ++j)
		left[j] = arr[i];

	for(int i=m+1, j=0; i<=r; ++i, ++j)
		rigth[j] = arr[i];
	
	int i = 0, j = 0, l =l_;

	while(i < m-l_+1 && j < r-m){
		if(left[i] <= rigth[j]) arr[l++] = left[i++];
		else arr[l++] = rigth[j++];
	}
	
	while(i < m-l_+1)
		arr[l++] = left[i++];

	while(j < r-m)
		arr[l++] = rigth[j++];
}

void mergeSort(vector<int> &arr, int l, int r){
	if(l >= r) return;
	else{
		int m = l + (r - l)/2;
		mergeSort(arr, l, m);
		mergeSort(arr, m+1, r);
		merge(arr, l, m, r);
	}
}

int main(){

	int n; cin >> n;
	vector<int> arr(n);

	for(int &i: arr) cin >> i;
	mergeSort(arr, 0, n-1);
	for(int i: arr) cout << i << " ";

	return 0;
}