#include <stdio.h>

#define MAX_DATA 10
int temp[MAX_DATA];/* 最小でも配列と同じサイズの領域が必要 */

void MergeSort(int x[ ], int left, int right);
void main(void);
void MergeSort(int x[ ], int left, int right)
{
    int mid, i, j, k;
	
    if (left >= right)              /* 配列の要素がひとつなら */
        return;                     /* 何もしないで戻る */

                                    /* ここでは分割しているだけ */
    mid = (left + right) / 2;       /* 中央の値より */
    MergeSort(x, left, mid);        /* 左を再帰呼び出し */
    MergeSort(x, mid + 1, right);   /* 右を再帰呼び出し */

    for (i = left; i <= mid; i++)
        temp[i] = x[i];

    for (i = mid + 1, j = right; i <= right; i++, j--)
        temp[i] = x[j];

    i = left;         
    j = right;        

    for (k = left; k <= right; k++)    
        if (temp[i] <= temp[j])        
            x[k] = temp[i++];
        else
            x[k] = temp[j--];
}

void main(void)
{
    int i;
     
    int x[ ] = {9, 4, 6, 2, 1, 8, 0, 3, 7, 5};
    for (i = 0; i < MAX_DATA; i++)
        printf("%d\t", x[i]);
    MergeSort(x, 0, MAX_DATA - 1);
    for (i = 0; i < MAX_DATA; i++)
        printf("%d\t", x[i]);
}
