#include<iostream>
using namespace std;
void merge(
int a[],
int low,
int mid,
int high){
int b[
100];
int i, j, k;
for (
int k = low; k <= high; k++)
b[k] = a[k];
for (i = low, j = mid +
1, k = i; i <= mid&&j <= high;){
if (b[i] < b[j])
a[k] = b[i++];
else
a[k] = b[j++];
k++;
}
while (i <= mid) a[k++] = b[i++];
while (j <= high) a[k++] = b[j++];
}
void mergeSort(
int a[],
int low,
int high){
if (low >= high)
return;
int mid = (low + high) /
2;
mergeSort(a, low, mid);
mergeSort(a, mid +
1, high);
merge(a, low, mid, high);
}
int main(){
int a[] = {
9,
8,
7,
6,
5,
4,
3,
2,
1 };
mergeSort(a,
0,
8);
for (
int i =
0; i <=
8; i++)
cout << a[i] << endl;
}