#include <iostream>
using namespace std;
int a[50];
void merge(int,int,int);
void merge_sort(int s,int d)
{
	int mid;
	if(s<d)
	{
		mid=(s+d)/2;
		merge_sort(s,mid);
		merge_sort(mid+1,d);
		merge(s,mid,d);
	}
}
void merge(int s,int mid,int d)
{
	
	int h,i,j,b[50],k;
	h=s;
	i=s;
	j=mid+1;
	while((h<=mid)&&(j<=d))
	{
		if(a[h]<=a[j])
		{
		   b[i]=a[h];
		   h++;
		}
		else
		{
		   b[i]=a[j];
		   j++;
		}
		i++;
	}
	if(h>mid)
	{
		for(k=j;k<=d;k++)
		{
			b[i]=a[k];
			i++;
		}
	}
	else
	{
		for(k=h;k<=mid;k++)
		{
			b[i]=a[k];
			i++;
		}
	}
	for(k=s;k<=d;k++) 
		a[k]=b[k];
}
int main()
{
 int n,i;
 cout<<"Nr de elemente:";cin>>n;
 cout<<"Elementele vectorului: "<<endl;
 for(i=1;i<=n;i++)
 {
	cout<<"a["<<i<<"]=";
	cin>>a[i];
 }
 merge_sort(1,n);
 cout<<"Noul vector sortat:"<<endl;
 for(i=1;i<=n;i++)
	cout<<a[i]<<"  ";
}