#include <stdio.h>
#include <string.h>

void merge(int input[], int left, int mid, int right);

void mergesort(int input[], int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;
    mergesort(input, left, mid);
    mergesort(input, mid + 1, right);
    merge(input, left, mid, right);
  }
}

int sortedarray[1000];

void merge(int input[], int left, int mid, int right) {
  int leftindex = left;
  int rightindex = mid + 1;
  int index = left;

  while (leftindex <= mid && rightindex <= right) {
    if (input[leftindex] < input[rightindex]) {
      sortedarray[index] = input[leftindex];
      leftindex++;
    } else {
      sortedarray[index] = input[rightindex];
      rightindex++;
    }
    index++;
  }

  while (leftindex <= mid) {
    sortedarray[index] = input[leftindex];
    index++;
    leftindex++;
  }
  while (rightindex <= right) {
    sortedarray[index] = input[rightindex];
    index++;
    rightindex++;
  }
  
  if(left < right)
  	memcpy(input + left, sortedarray + left, sizeof(int) * (right - left + 1));
}

int main() {
	int i;
	int data[] = {1, 2, 9, 7, 9, 4, 10, 100, 99, 77, 1, 1000};
	
	mergesort(data, 0, sizeof data / sizeof data[0] - 1);
	
	for(i = 0; i < sizeof data / sizeof data[0]; ++i)
		printf("%d ", sortedarray[i]);
		
	putchar('\n');
	return 0;
}