#include <iostream>

using namespace std;

int a[] = {9,3,1,4,5,7,7,2,2};

void merge(int a[], int left, int m, int right) {
  int n1 = m-left+1;
  int n2 = right-m;
  int L[n1];
  int R[n2];

  for (int i=0; i< n1; i++)
    L[i] = a[left+i];
  for (int i=0; i< n2; i++)
    R[i] = a[m+i+1];

  int i = 0;
  int j = 0;
  int k = left;

  while(i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      a[k] = L[i];
      i++;
      k++;
    } else {
      a[k] = R[j];
      j++;
      k++;
    }
  }
  while(i<n1) {
    a[k] = L[i];
    i++;
    k++;
  }
  while(j<n2) {
    a[k] = R[j];
    j++;
    k++;
  }
}

void merge_sort(int a[], int left, int right) {
  if (left < right) {
    int m = (right+left)/2;
    merge_sort(a, left, m);
    merge_sort(a, m+1, right);
    merge(a, left, m, right);
  }
}

int main() {
  int n = sizeof(a)/sizeof(a[0]);
  merge_sort(a, 0, n-1);

  for (int i=0;i<n;i++) {
    cout << a[i] << " ";
  }
  cout << "\n";
  return 1;
}