#include <stdio.h>

#define DATA_NUM 10

void sortMerge(int *data, int dataNum, int left, int right){
   int tmp[DATA_NUM];
   int i, j, k;
   int middle;

   // 配列の要素が１個であればreturn
   if(left >= right){
       return;
   }

   middle = (left + right) / 2;

   // 左側を再帰
   sortMerge(data, dataNum, left, middle);
   // 右側を再起
   sortMerge(data, dataNum, middle + 1, right);

   // data[left] から data[midddle] をtmp領域にコピー
   for(i = left; i <= middle; i++){
       tmp[i] = data[i];
   }
   // data[middle + 1] から data[right] を逆順でtmp領域にコピー
   for(i = middle + 1, j = right; i <= right; ++i, --j){
       tmp[i] = data[j];
   }

   i = left;
   j = right;

   // ソート
   for (k = left; k <= right; k++){
       if(tmp[i] <= tmp[j]){
           data[k] = tmp[i];
           ++i;
       } else {
           data[k] = tmp[j];
           --j;
       }
   }
}

int main(){
   int data[DATA_NUM] = {2, 6, 9, 1, 0, 3, 5, 8, 4, 7};
   int i;

   printf("before : ");
   for(i = 0; i < DATA_NUM; ++i){
      printf("%d ", data[i]);
   }
   printf("\n");

   sortMerge(data, 10, 0, DATA_NUM - 1);
   
   printf("after  : ");
   for(i = 0; i < DATA_NUM; ++i){
      printf("%d ", data[i]);
   }
   printf("\n");

   return 0;
}