归并排序

归并排序

二路归并排序

1. 初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列

2. 对所有有序子序列进行两两归并，得到n/2个长度为2或1的有序子序列–一趟归并

3. 重复步骤2，直到得到长度为n的有序序列为止

• 上述排列过程中，子序列总是两两归并，称为2路归并排序。其核心是如何将相邻的两个子序列归并成一个子序列。

• 设相邻的两个子序列分别为：

• {R[k]，R[k+1]，…R[m]}和{R[m+1]，R[m+1]，…R[h]}

• 将它们归并为一个有序的子序列

• {DR[1]，DR[1+1]，…，DR[m]，…，DR[m]，DR[m+1]，…，DR[h]}。

• 设有9个待排序的记录，关键字分别为

{23, 38, 22, 45, 23, 67, 31, 15, 41}

• 初始关键字：{ [23] [38] } { [22] [45] } { [23] [67] } { [31] [15] } [41]

• 第一趟：{ [23] [38] } { [22] [45] } { [23] [67] } { [15] [31] } [41]

• 第二趟：{ [22] [23] [38] [45] } { [15] [23] [31] [67] } [41]

• 第三趟：{ [15] [22] [23] [23] [31] [38] [45] [67] } [41]

• 第四趟：{ [15] [22] [23] [23] [31] [38] [41] [45] [67] }

void mergeSort(int A[], int low, int high){
	if(low < high){
		int mid = (low + high) / 2;
		mergeSort(A, low, mid);
		mergeSort(A, mid + 1, high);
		mergeSort(A, low, mid, high);
	
	}
}