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

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

*/