歸并排序 O(N*logN) 是另一種效率很高的排序方法。"歸并"的含義就是將兩個或兩個以上的有序表組合成一個有序表。加入兩個有序表的長度分別為m、n，則一次歸并的時間復雜度為O(m+n)。

?

我們可以用"歸并"的思想來實現排序。假如待排序列含有n個關鍵字，則可看成是n個有序的子序列，每個序列長度為1，然后兩兩歸并，得到[n/2]個長度為2或1的子序列，在兩兩歸并....，知道得到一個長度為n的有序序列為止。這就是2-路歸并算法。

?

下圖就是2-路歸并排序的一個例子：

?

我們可以用分治的思想解決歸并排序，給定一個有N個關鍵字的有序序列，分治法的步驟如下：

(1)劃分： 如果S中有1個元素，則直接返回S，因為它已經有序了。否則(S中至少有兩個元素)，把它們分別放入兩個序列S1和S2中，S1和S2各包含大約S中的一半元素，即S1包含S中的前[N/2]個元素，S2包含S中的后[N/2]個元素。

(2)遞歸：遞歸求解子問題S1和S2。

(3)求解：歸并有序序列S1和S2，使得他們成為一個有序序列，將其中的元素放回S中。

    #include<iostream.h>
#include<malloc.h>
/************************  
 * 歸并排序 Merge Sort  *   
 ***********************/   
class MergeSort{
public:
	//遞增排序
	static void inc_sort(int keys[], int size);
private:
	//歸并排序算法
	static void merge_sort(int raw[], int *merged, int s, int t);
	//歸并
	static void merge(int raw[], int *merged, int si, int mi, int ti);
};

void MergeSort:: merge(int raw[], int *merged, int si, int mi, int ti){

	//把已近排序號的si-mi，mi-ti兩個序列賦值給raw
	for(int t=si;t<=ti;t++)
			raw[t]=merged[t];
	//歸并
	int i=si,j=mi+1,k=si;
	for(;i<=mi&&j<=ti;){
		if(raw[i]<=raw[j]) merged[k++]=raw[i++];
		else merged[k++]=raw[j++];
	}
	if(i<=mi)
		for(int x=i;x<=mi;)
			merged[k++]=raw[x++];
	if(j<=ti)
		for(int y=j;y<=ti;)
			merged[k++]=raw[y++];
}
//劃分
void MergeSort:: merge_sort(int raw[], int *merged, int s, int t){

	if(s==t) merged[s]=raw[s];
	else{
		int m=(s+t)/2;
		MergeSort::merge_sort(raw, merged, s, m);
		MergeSort::merge_sort(raw, merged, m+1,t);
		MergeSort::merge(raw, merged, s,m,t);
	}
}

void MergeSort:: inc_sort(int keys[],int size){

	int * merged=(int *)malloc(size*sizeof(int));
	MergeSort::merge_sort(keys,merged,0,size-1);
	//打印排序結果
	for(int i=0;i<size;i++)
		cout<<merged[i]<<" ";
	cout<<endl;

	free(merged);
}
//Test MergeSort
void main(){
	int raw[]={49,38,65,97,76,13,27,49};   
	int size=sizeof(raw)/sizeof(int);     
	MergeSort::inc_sort(raw,size);    
}
  

?

?代價分析：
上圖可以看出，一個N關鍵字的序列，兩兩歸并可以構造一棵高度為[logN]的歸并排序樹。而每一次歸并的時間復雜度為O(m+n)。因此每一趟歸并的時間復雜度為O(N)，如上圖。歸并排序算法的 總時間復雜度為O(N*logN) 。其所需要的輔助空間就是一個能容納中間合并結果的數量為N的連續空間。因此 空間復雜度為O(N) 。是 穩定排序方法 。

?

?

?

【排序結構4】 歸并排序