前言

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序演算法,該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，其中二路歸并類似二叉樹的后序遍歷，歸并排序的思考更多的是解決在磁盤中的外排序問題，

主要思路：

■ 先將待排序的序列分割為小的序列，使每個子序列有序，

■ 將小的子序列合并為更大的子序列，即使子序列段間有序，合并到最后整個序列有序，

程序演示

遞回實作歸并排序

C語言代碼實作

//將已有序的小區間合并為更大的有序區間，其中合并取得是閉區間，
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int *temp) {
	int index = begin1;
	int left = begin1, right = end2;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) temp[index++] = a[begin1++];
		else temp[index++] = a[begin2++];
	}
	while(begin1<=end1)temp[index++] = a[begin1++];
	while(begin2<=end2)temp[index++] = a[begin2++];
	for (int i = left; i <= right;++i) a[i] = temp[i];
}
//遞回處理更小的區間序列
void _MergeSort(int *a,int left,int right,int *temp) {
	if (left >= right) return;//當區間只有一個元素或沒有元素時回傳
	int mid = (left + right) >> 1;//以每個區間的中點分割區間
	_MergeSort(a,left,mid,temp);//遞回處理左區間
	_MergeSort(a,mid+1,right,temp);//遞回處理右區間
	MergeArr(a,left,mid,mid+1,right,temp);//合并為更大的有序區間
}

//歸并遞回
void MergeSort(int *a,int n) {
	assert(a);
	int* temp = (int*)malloc(sizeof(int)*n); 
	if(temp==NULL){
		printf("申請空間失敗!!!\n");
		exit(-1);
	}
	_MergeSort(a,0,n-1,temp);
	free(temp);
}

非遞回實作歸并排序

程序如下圖！！！

C語言代碼實作

//將已有序的小區間合并為更大的有序區間，其中合并取得是閉區間，
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int *temp) {
	int index = begin1;
	int left = begin1, right = end2;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) temp[index++] = a[begin1++];
		else temp[index++] = a[begin2++];
	}
	while(begin1<=end1)temp[index++] = a[begin1++];
	while(begin2<=end2)temp[index++] = a[begin2++];
	for (int i = left; i <= right;++i) a[i] = temp[i];
}
//歸并非遞回實作
void MergeSortNonR(int* a, int n) {
	assert(a);
	int* temp = (int*)malloc(sizeof(int)*n);
	if(temp==NULL){
		printf("申請空間失敗!!!\n");
		exit(-1);
	}
	int gap = 1;//其中gap的含義代表本次回圈合并的數字個數
	while (gap < n) {
		for (int i = 0; i < n; i += 2 * gap) {
			//因為是閉區間，所以end的大小要 -1;
			int begin1=i, end1 =i+gap-1;
			
			int begin2=i+gap, end2 =i+2*gap-1;
			
			if (begin2 >= n) break;//當第二段區間不存在時，只存在第一段區間時，結束回圈，如果只存在第一段區間則不用合并!!!!
			if (end2 >= n) end2 = n - 1;//當第二段區間存在并且end2>=n 時縮小第二段區間的范圍，
			
			MergeArr(a,begin1,end1,begin2,end2,temp);
		}
		gap *= 2;
	}
	free(temp);
}

使用歸并排序完成磁盤中的外排序

問題：當有一個檔案中放置著以某種格式存在的海量資料，我們無法一次性將資料全部加載進入記憶體中，此時要求我們完成對這個檔案的排序，

思路：

■ 將大檔案先分割成多個小檔案，

■ 將大檔案中的部分資料加載進入記憶體中，為了節省空間我們可以使用快速排序，將這部分資料排序，然后將排好的資料輸出到小檔案中，

■ 重復上述程序直到將大檔案中的資料全部形成小檔案，

■ 合并小檔案形成更大的檔案，然后將這個更大的檔案接著和剩下的小檔案進行合并，重復此程序直到小檔案最終被合并完畢，這樣就形成了最終排好序的大檔案，

程序實作如下圖！！！

C語言代碼實作

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

void MergeFile(const char*sin1,const char *sin2,const char*sout) {
	FILE* file1 = fopen(sin1,"r");
	if (file1 == NULL) {
		printf("file1打開檔案失敗！！\n");
		exit(-1);
	}
	FILE* file2 = fopen(sin2, "r");
	if (file2 == NULL) {
		printf("file2打開檔案失敗！！\n");
		exit(-1);
	}
	FILE* fout = fopen(sout,"w");
	if (fout == NULL) {
		printf("fout打開檔案失敗！！\n");
		exit(-1);
	}
	int num1, num2;
	int flag1 = fscanf(file1,"%d ",&num1);
	int flag2 = fscanf(file2, "%d ", &num2);
	while (flag1!=EOF&&flag2!= EOF) {
		if (num1 < num2) {
			fprintf(fout,"%d ",num1);
			flag1 = fscanf(file1, "%d ", &num1);
		}
		else {
			fprintf(fout, "%d ", num2);
			flag2 = fscanf(file2, "%d ", &num2);
		}
	}
	while (flag1 != EOF) {
		fprintf(fout, "%d ", num1);
		flag1 = fscanf(file1, "%d ", &num1);
	}
	while (flag2 != EOF) {
		fprintf(fout, "%d ", num2);
		flag2 = fscanf(file2, "%d ", &num2);
	}
	fclose(file1);
	fclose(file2);
	fclose(fout);
}
//file檔案的名字，N生成小檔案的數量，Nnum一個小檔案中包含多少個數
void MergeSortFile(const char* file, const int N, const int Nnum) {
	FILE* fout = fopen(file, "r"); //讀取這個大檔案
	int* temp = (int*)malloc(sizeof(int) * Nnum); //保存從檔案中輸出的資料
	if (temp == NULL) {
		printf("記憶體不足、申請失敗!!\n");
		exit(-1);
	}
	char subfile[20];	//保存每個小檔案的檔案名
	int i = 0, filei = 1;//i 用作陣列索引，filei代表第幾個小檔案
	int num;	//保存從檔案中讀入的每個資料
	while (fscanf(fout, "%d ", &num) != EOF) {
		if (i < Nnum - 1) {//i<Nnum-1
			temp[i++] = num;//將從大檔案中讀入的資料保存到陣列中
		}
		else {
			temp[i] = num;
			QuickSortNonR(temp, 0, Nnum - 1);//用快速排序將陣列的資料進行排序，這個函式需要自己寫，
			sprintf(subfile, "sub\\subsort%d", filei++);//生成檔案名
			FILE* fin = fopen(subfile, "w");//打開小檔案
			if (fin == NULL) {
				printf("打開檔案失敗！！！");
				exit(-1);
			}
			for (int j = 0; j < Nnum; j++) {
				fprintf(fin, "%d ", temp[j]);//將陣列中的資料保存到小檔案中
			}
			fclose(fin);
			i = 0;
			printf("subsort%d已完成排序！！！！\n",filei-1);
		}
	}
	printf("小檔案排序完成！！！！\n");
	const char prefixout[50] = "sub\\mergefile";
	const char prefixin[50] = "sub\\subsort";
	char fmout[50]="sub\\mergefile1";
	char fin1[50]="sub\\subsort1";
	char fin2[50]="sub\\subsort2";
	for (int i = 2; i <= N; i++) {
		MergeFile(fin1,fin2, fmout);
		printf("%s合并完畢\n", fmout);
		strcpy(fin1, fmout);
		strcpy(fmout, prefixout);
		strcpy(fin2, prefixin);
		sprintf(fmout,"%s%d%s",fmout,i);
		sprintf(fin2,"%s%d%s",fin2,i+1);
	}
	fclose(fout);
}

int main() {
	srand(time(0));
	char sfile[30] = "e:\\random.txt";	
	const int N=10,Nnum= 5000000;
	FILE* file = fopen(sfile, "w");
	if (file == NULL) {
		printf("open fail!!!\n");
		exit(-1);
	}
	else {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < Nnum; j++) {
				fprintf(file, "%d ", rand());
			}
		}
		fclose(file);
	}
	//以上程序實作生成一個大檔案，
	printf("生成亂數完成!!!!\n");
	printf("小檔案開始分解排序!!!!\n");
	MergeSortFile(sfile,N,Nnum);
	printf("小檔案合并完成!!!!\n");
	return 0;
}

歸并排序的特性總結

1、歸并排序的缺點在于需要額外的O(n)的空間，空間復雜度：O(n)，但是有個優點就是可以用作外排序，其中使用外排序實際就是把檔案當作陣列來進行，我們用歸并排序實作外排序可以解決磁盤中的外排序，
2、時間復雜度：O(nlongn)，其中最好和最壞時間復雜度都是O(nlogn)，
3、穩定性：穩定，