---
tags: codebook
---
{%hackmd theme-dark %}
# merge sort(iterator)

#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
template<typename T>
void merge_sort(__gnu_cxx::__normal_iterator<T*,vector<T>> l,__gnu_cxx::__normal_iterator<T*,vector<T>> r){
	if(distance(l,r)==1) return;
	auto mid=l+distance(l,r)/2;
	vector<T> lsub(l,mid);
	vector<T> rsub(mid,r);
	merge_sort(lsub.begin(),lsub.end());
	merge_sort(rsub.begin(),rsub.end());
	auto lpivot=lsub.begin(),rpivot=rsub.begin();
	while(lpivot!=lsub.end()&&rpivot!=rsub.end())
		*l++=((*lpivot<*rpivot)?*lpivot++:*rpivot++);
	while(lpivot!=lsub.end())
		*l++=*lpivot++;
	while(rpivot!=rsub.end())
		*l++=*rpivot++;
}
int main(){
	size_t n;
	while(cin>>n){
		vector<long long int> vec(n);
		for(auto& i:vec) cin>>i;
		merge_sort(vec.begin(),vec.end());
		for(const auto& i:vec) cout<<i<<(--n?" ":"");
		cout<<endl;
	}
	return 0;
}