#include <stdio.h>

void osszefesul(int a[], int p, int q, int r)
{
	int n1 = q-p+1;
	int n2 = r-q;
	
	int bal[n1];
	int jobb[n2];
	int i, j, k;
	
	for(i=0; i<n1; i++)
		bal[i] = a[p+i];
	
	for(j=0; j<n2; j++)
		jobb[j] =a[q+j+1];
	
	bal[n1] = 1000;
	jobb[n2] = 1000;
	i=0;
	j=0;
	
	for(k=p ; k<=r;k++)
		if(bal[i]<=jobb[j])
		{
			a[k] = bal[i];
			i++;
		}
		else
		{
			a[k] = jobb[j];
			j++;
		}
}

void osszefesulorendezes(int tomb[], int p, int r)
{
	if(p<r)
	{
		int q=(p+r)/2;
		osszefesulorendezes(tomb, p, q);
		osszefesulorendezes(tomb, q + 1, r);
		osszefesul(tomb, p, q, r);		
	}
}


main()
{	
	int tomb[] = {8, 3, 4, 5, 2, 9, 7};	
	
	osszefesulorendezes(tomb, 0, 6);
	
	int i;
	for(i=0; i<7;i++)
		printf("%d ", tomb[i]);
	printf("\n");
	
}