#include <stdio.h>

void Mpass(int x[],int y[],int k,int n);	/*聲明其為函數*/
void Msort(int x[],int y[],int n);			/*聲明其為函數*/

int main(void)
{
	/*要排序整型數據序列*/
	int a[] = {26,5,37,1,61,11,59,15,48,19};
	int y[10];				/*用于暫時存儲數據*/
	int i;
	printf("源數據為：	   ");	/*將源數據打印出來*/
	for(i = 0;i<10;i++)
	printf("[%2d]",a[i]);
	Msort(a,y,10);		/*對源數據進行合并排序*/
	printf("\n排序后的數據為:  ");
	for(i = 0;i<10;i++)			/*將排序結果打印出來*/
	printf("%4d",a[i]);
	printf("\n");
	return 0;
}

void Mpass(x,y,k,n)
int x[];					/*要排序的數組*/
int y[];					/*用于存儲臨時數據的數組*/
int k;				/*表示當前序列中有若干長度為k的相鄰有序子序*/
int n;				/*要排序序列的長度為n*/
	
{
	int i,j;
	int	strat1,end1;	/*對應第一個有序子序列L1起始和終止位置號*/
	int	strat2,end2;	/*對應第二個有序子序列L2起始和終止位置號*/
	int	m;				/*表示輸入y中當前記錄應放置的位置號*/
	strat1 = 0;
	m = 0;
	while(strat1+k<=n-1)		/*當第一個子序列沒有占據整個x數組*/
	{
		strat2 = strat1+k;		/*為兩個有序子序列起始終止位置號賦值*/
		end1 = strat2-1;
		/*如果第二的子序列長度不夠k，則其終止位置號為n-1*/
		end2 = (strat2+k-1<=n-1)?strat2+k-1:n-1;
		for(i = strat1,j = strat2;i<=end1&&j<=end2;m++)
		{
			if(x[i]<=x[j])
			{
				y[m] = x[i];
				i++;
			}
			else
			{
				y[m] = x[j];
				j++;
			}
		}
		while(i<= end1)
		{
			y[m] = x[i];
			m++;
			i++;
		}
		while(j<= end2)
		{
			y[m] = x[j];
			m++;
			j++;
		}
		strat1 = end2+1;
	}
	/*將另一個序列中剩余的所有記錄依次放到數組y中*/
	for(i=strat1;i<n;i++,m++)		
		y[m] = x[i];
}

void Msort(x,y,n)
int x[];			/*要排序的數組*/
int y[];			/*用于存儲臨時數據的數組*/
int n;				/*數組長度*/
{
	int i,k,count;
	k = 1;
	count = 1;
	while(k<n)				/*當子序列比整個序列小時*/
	{
		Mpass(x,y,k,n);		/*歸并兩有序子序列*/	
		for(i= 0;i<n;i++)
			x[i] = y[i];	/*返回數據*/
		printf("\n第%2d步后的結果==>  ",count++);
			for(i = 1;i<n+1;i++)
		{
			if((i ==n)&&((i%(2*k)!=0)))
				printf("%4d]",x[i-1]);
			else
			{
				if((i%(2*k)==1))
					printf("[%2d",x[i-1]);
				else if((i%(2*k))==0)
					printf("%4d]",x[i-1]);
				else
					printf("%4d",x[i-1]);
			}
		}
		k = 2*k;		/*一次歸并后新的有序子序列的長度*/
	}
}