合并排序的三種不同寫法，包括遞歸和非遞歸

       在學算法設計課中，學到合并排序時，并把合并排序的三種不同的寫法都寫了一遍（兩種遞歸的形式其實大同小異，隻是在一種寫法中整個算法隻配置設定了一個臨時數組而一種寫法中每次遞歸時都會配置設定臨時空間用于暫存資料）。

一、遞歸形式的一種寫法（每次遞歸操作中都配置設定新的空間）

void merge1(item * A, item * B, item * C, int Lb, int Lc){
	int i = 0, j = 0, k = 0;
	while(i < Lb && j < Lc){
		if(B[i] <= C[j] )
			A[k++] = B[i++];
		else
			A[k++] = C[j++];
	}
	if(i < Lb)
		while(i < Lb)
			A[k++] = B[i++];
	else
		while(j < Lc)
			A[k++] = C[j++];
}

/*    A為待排序數組  n為數組長度    */
void merge_sort1(item * A, int n){
	if(n > 1){
		int m = n/2;
		item * B = new int[m + 1];//将數組A元素複制到數組B與C
		item * C = new int[m + 1];
		int i;
		for(i = 0; i < m; i++)
			B[i] = A[i];
		for(i = 0; i < n - m; i++)
			C[i] = A[i + m];
		merge_sort1(B, m);//遞歸調用
		merge_sort1(C, n - m);
		merge1(A, B, C, m , n - m);//合并兩個有序數組
	}
 }
           
   

二、遞歸形式的第二種寫法（整個算法隻new了一個臨時數組，後面操作都共用）

typedef int item;
void merge2(item * p, item * q, int first, int mid, int last){
	int f = first, j = mid + 1, k = 0;
	while(f <= mid && j <= last){
		if(p[f] < p[j]){
			q[k ++] = p[f ++];
		}
		else{
			q[k ++] = p[j ++];
		}
	}
	if(f <= mid){
		while(f <= mid)
			q[k ++] = p[f ++];
	}else
		while(j <= last)
			q[k ++] = p[j ++];
	int i;
	for(i = 0; i < k; i++)//将已排序數組複制到原數組
		p[first + i] = q[i];
}

/*     p為待排序數組, q為臨時數組    */
void merge_sort2(item *p, item *q, int n1, int n2){
	if(n1 < n2){
		int m = (n1 + n2)/2;
		merge_sort2(p, q, n1, m);
		merge_sort2(p, q, m + 1, n2);
		merge2(p, q, n1, m, n2);
	}
}
           

三、非遞歸形式       原來的遞歸過程是将待排序集合一分為二，直至排序集合就剩下一個元素位置，然後不斷的合并兩個排好序的數組。而非遞歸思想為，将數組中的相鄰元素兩兩配對，并将其排序，構成n/2組長度為2的排序好的子數組段，然後再将他們排序成長度為4的子數組段，如此繼續下去，直至整個數組排好序。

typedef int item;

void merge3(item * p, int first, int mid, int last){
	if(mid > last)//重要的判斷
		return;
	int f = first, j = mid + 1, k = 0;
	item *q = new item[last - first + 1];//用于暫時存放的數組
	while(f <= mid && j <= last){
		if(p[f] < p[j]){
			q[k ++] = p[f ++];
		}
		else{
			q[k ++] = p[j ++];
		}
	}
	if(f <= mid){
		while(f <= mid)
			q[k ++] = p[f ++];
	}else
		while(j <= last)
			q[k ++] = p[j ++];
	int i;
	for(i = 0; i < k; i++)//将已排序數組複制到原數組
		p[first + i] = q[i];
}

/*    p為待排序數組  n為數組長度   */
void merge_sort3(item * p, int n){
	int i, m = 2;
	while(m <= n){
		i = 0;//!
		while(i + m <= n){
			merge3(p, i, i + m/2 - 1, i + m -1);
			i += m;
		}
		merge3(p, i, i + m/2 - 1, n -1);//尾部殘餘處理
		m *= 2;
	}
	merge3(p, 0, m/2 - 1, n - 1);//最後一次對兩個有序數組做合并排序
}
           

    在三種算法中，實際運作發現過多的new會花費很多時間，是以遞歸的第二種形式要明顯由于第一種。