#include<stdio.h>
void mergearray(int a[], int first, int mid, int last,int temp[])
{
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;
    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= m)
        temp[k++] = a[i++];
    while (j <= n)
        temp[k++] = a[j++];
    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);         //对左侧排序
        mergesort(a, mid + 1, last, temp);      //对右侧排序
        mergearray(a, first, mid, last, temp);  //合并
    }
}
int main()
{
    int n,i,j,a[100],temp[100];
    printf("请输入数组元素个数：\n");
    scanf("%d",&n);
    printf("请分别输入%d个数组元素：\n",n);
    for (i = 0; i < n; i++)
        scanf("%d",&a[i]);
    mergesort(a, 0, n-1, temp);
    printf("排序后的数组为：\n");
    for (i = 0; i < n; i++)
        printf("%d ",a[i]);
    return 0;
}