#include<stdio.h>
#include<stdlib.h>
#define MAX 500001
int array[MAX], array1[MAX];
__int64 sum;
void MergeSort(int, int);
void Merge(int, int, int);

int main()
{
    int n, m, i, j = 0;
    while (1)
    {
        sum = 0;
        scanf("%d", &m);
        if (m == 0)
        {
            break;
        }
        for (i = 0; i < m; i++)
        {
            scanf("%d", &array[i]);
        }
        MergeSort(0, m - 1);
        printf("排序结果\n"); 
        for (i = 0; i < m; i++)
        {
            printf("%d\t", array[i]);
        }
    }
    system("pause");
    return 0;
}

void MergeSort(int i, int j)
{
    int h;
    if (i < j)
    {
        /* 将长度为m的输入序列分成两个长度为n/2的子序列 */
        h = (i + j)/2;
        printf("i = %d h = %d j = %d\n", i, h, j);
        /* 对两个子序列分别进行归并排序 */
        MergeSort(i, h);
        MergeSort(h + 1, j);
        /* 将2个排好的子序列合并成最终有序序列 */
        Merge(i, h, j);
    }
}
void Merge(int i, int h, int j)
{
    int k = 0, y = h + 1, x = i;
     /* 2个输入区间都不为空时 */

    while (x <= h && y <= j)
    {
        /* 取关键字小的记录转移至输出区间 */

        if (array[x] > array[y])
        {
            array1[k++] = array[y++];
            sum += h - x + 1;
        }
        else
        {
            array1[k++] = array[x++];
        }
    }
    /* 将非空的输入区间转移至输出区间 */
    while (x <= h)
    {
        array1[k++] = array[x++];
    }
    while (y <= j)
    {
        array1[k++] = array[y++];
    }
     /* 归并完成后将结果复制到原输入数组 */

    printf("当前结果\n"); 
    for(x = 0; x < k; x++)
    {
        array[i + x] = array1[x];
        printf("%d ", array[i + x]);
    }
    printf("\n");
}
/*
6
1 2 5 6 3 4

*/