#include  "datastru.h"
#include  <stdio.h>

void merge(RECNODE *r, int low, int m, int high)
{/*兩相鄰的有序表(一個從low到m;另一個從m+1到high)合并為一個有序表(從low到high)*/
 	RECNODE  r1[MAXSIZE];             /*合并時用的緩沖向量*/
	int i, j, k;

	i = low;
	j = m + 1;
	k = 0;
	while(i <= m && j <= high)              /*兩相鄰的有序表合并*/
	  if(r[i].key <= r[j].key)
	    {r1[k] = r[i];  i++;  k++;}
	  else
	    {r1[k] = r[j];  j++;  k++;}
	while(i <= m)                           /*有序表剩余部分處理*/
	   {r1[k] = r[i];  i++;  k++;}
	while(j <= high)                        /*有序表剩余部分處理*/
	   {r1[k] = r[j];  j++;  k++;}
	for(i = low, k = 0; i <= high; i++, k++)/*緩沖向量r1復制到原來的r中*/
	   r[i] = r1[k];

}

void merge_one(RECNODE *r, int lenth, int n)
{/*二路歸并中的"一趟歸并"算法*/
	int i = 0;

	while(i + 2 * lenth - 1 < n)
	  {merge(r, i, i + lenth - 1, i + 2 * lenth - 1);/*兩子序列長度相等的*/
	   i = i + 2 * lenth;}                           /*情況下調用merge*/
	if(i + lenth - 1 < n - 1)
	   merge(r, i, i + lenth - 1, n - 1);            /*序列中的余留部分處理*/
}

void mergesort(RECNODE *r, int n)
{/*二路歸并排序算法*/
	int lenth = 1;                 /*有序子序列長度初始值 = 1*/

	while(lenth < n)
	  {merge_one(r, lenth, n);     /*調用"一趟歸并"的算法*/
	   lenth = 2 * lenth;}         /*有序子序列長度加倍*/
}

main( )
{ RECNODE  a[MAXSIZE];
  int  i, j, k, len;

 printf("\n\n輸入待排序數據(整數，以空格隔開，0 結束) : "); k = 0; scanf("%d",&j);
 while(j != 0) { k++; a[k-1].key = j; scanf("%d",&j); }
 len = k;
 printf("\n排序前 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i].key);
 printf("\n");
 mergesort (a,len);
 printf("\n");
 printf("\n\n排序后 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i].key);
 printf("\n");
}