#include <iostream>
using namespace std;

void mergesort (int a[], int low, int high);
void merge (int a[], int low, int high);

int main ()
{
	int a[]={1,8,4,90,33,67,22,76,43};
	int low=0, high=8;
	int i;
	
	mergesort (a, low, high);
	for (i=0; i<9; i++)
	cout << a[i] << " ";
	return 0;
}

void mergesort (int a[], int low, int high)
{	
	int m;
	if (low<high)
	{
		m=(low+high)/2;
		mergesort (a, low, m);
		mergesort (a, m+1, high);
		merge (a, low, high);
	}
}

void merge (int a[], int low, int high)
{	
	int n=high-low+1;
	int b[n]; //Temporary
	int k=0, m, i, j;

	m=(low+high)/2;
	for (i=low; i<=m; i++)
		b[k++]=a[i];

	for (j=high; j>=m+1; j--)
		b[k++]=a[j];
	
	i=0; j=n-1; k=low;

	while (i<=j)
		if (b[i]<=b[j])
			a[k++]=b[i++];
		else
			a[k++]=b[j--];
}