#include <iostream>
void mergesort(int *a, int n);
void osszefesules(int *a, int n);
void kiir(int a[], int n);
using namespace std;
int main() {
	int *a, n,i;
	cin >> n;
	a = (int*)malloc(n*sizeof(int));
	for (i = 0; i < n; ++i) {
		a[i] = rand() % 100;
	}

	kiir(a, n);
	mergesort(a, n);
	kiir(a, n);
		system("pause");
	return 0;

}
void mergesort(int *a, int n) {
	if (n > 1) {
		mergesort(a, n / 2 - 1);//elso fele n/2
		mergesort(a + n / 2, n - n / 2);
		osszefesules(a, n);
	}
}
void osszefesules(int *a, int n) {
	int i, j, k;
	int *b = a + n / 2;
	int m = n - n / 2;
	int *c = (int*)malloc(n*sizeof(int));
	n = n / 2;
	i = j = k = 0;

	while (i < n && j < m) {
		if (a[i] < b[j]) { c[k++] = a[i++]; }
		else { c[k++] = b[j++]; }
	}

	while (j < m) {
		c[k++] = b[j++];
	}

	while (i < n) {
		c[k++] = a[i++];


	}
	for (i = 0; i < n + m; ++i) {
		a[i] = c[i];
	}
}
void kiir(int a[], int n) {
	for (int i = 0; i < n; ++i) {
		cout << a[i] << " ";
	}
	cout << endl;
}
}