#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

void Merge(int R[],int low,int mid,int high)
//將兩個(gè)有序表R[low..mid]和R[mid+1..high]歸并為一個(gè)有序表R[low..high]
{
	int *R1;
	int i=low,j=mid+1,k=0;  //k是R1的下標(biāo)，i,j分別為第1,2段的下標(biāo)
	R1=(int *)malloc((high-low+1)*sizeof(int));  //R1為輔助數(shù)組

	while(i<=mid&&j<=high) //在第1段和第2段均未掃描完時(shí)循環(huán)
		if(R[i]<=R[j])    
		{
			R1[k]=R[i];	
			i++; k++;
		}
		else            
		{
			R1[k]=R[j];	
			j++; k++;
		}

	while(i<=mid)   //將第1段余下部分復(fù)制到R1
	{
		R1[k]=R[i];	
		i++; k++;
	}
	while(j<=high)  //將第2段余下部分復(fù)制到R1
	{
		R1[k]=R[j];
		j++; k++;
	}

	for(k=0,i=low; i<=high; k++,i++)  //將R1復(fù)制回R中
		R[i]=R1[k];
}

void MergePass(int R[],int length,int n)  //實(shí)現(xiàn)一趟歸并
{
	int i;
	for(i=0; i+2*length-1<n; i=i+2*length)  //歸并length長(zhǎng)的兩相鄰子表
		Merge(R,i,i+length-1,i+2*length-1);

	if(i+length-1<n)  //余下兩個(gè)子表，后者長(zhǎng)度小于length
		Merge(R,i,i+length-1,n-1);  //歸并這兩個(gè)子表
}

void MergeSort(int R[],int n)  //二路歸并排序算法
{
	int length,k,i=1;   //i用于累計(jì)歸并的趟數(shù)
	for(length=1;length<n;length=2*length)
	{
		MergePass(R,length,n);
		printf("  第%d趟歸并:\n",i++);   //輸出每一趟的排序結(jié)果
		for(k=0;k<n;k++)
			printf("%4d",R[k]);
		printf("\n");
	}
}

void main()
{
	int k,n=10;
	int a[]={18,2,20,34,12,32,6,16,7,14};

	printf("\n");
    printf("對(duì)數(shù)組中元素進(jìn)行歸并排序 ");
	printf("\n");

	printf("  初始關(guān)鍵字為:\n");
	for(k=0;k<n;k++)
		printf("%4d",a[k]);
    printf("\n");

	MergeSort(a,n);

	printf("  最后結(jié)果為:\n");
	for(k=0;k<n;k++)
		printf("%4d",a[k]);
	printf("\n");

	system("PAUSE");
}