#include <bits/stdc++.h>

using namespace std;

int b[100];

void MergeSort(int a[], int l, int r) {
	if (r > l) {
		int i, j;
		int m = (l + r) / 2;
		MergeSort(a, l, m);
		MergeSort(a, m + 1, r);
		for (i = m; i >= l; i--) b[i] = a[i];
		for (j = m + 1; j <= r; j++) b[r + m + 1 - j] = a[j];
		i = l; j = r;
		for (int k = l; k <= r; k++) {
			if (b[i] < b[j]) {
				a[k] = b[i];
				i++;
			} else {
				a[k] = b[j];
				j--;
			}
		}
	}
}

int main() {
	int a[8] = {1, 3, 4, 9, 6, 7, 5, 4};
	MergeSort(a, 0, 7);
	for (int i = 0; i < 8; i++) cout << a[i] << " ";
	return 0;
}