外部排序（归并排序）

 1 //二路一次归并过程的算法
 2 //low为本次二路归并排序的第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
 3 void merge(int List[], int low, int mid, int high)
 4 {
 5     //mid+1为第2有序区第1个元素，mid为第1有序区的最后1个元素
 6     //i 指向第 1 有序区的第 1 个元素
 7     int i = low;
 8     //j 指向第 2 有序区的第 1 个元素，high 为第 2 有序区的最后一个元素
 9     int j = mid + 1;
10     //temp数组暂存合并的有序序列
11     int *temp = new int[high - low + 1];
12     //设置临时数组的指示标志 k
13     int k = 0;
14     //内存分配失败
15     if(!temp){
16         cout<<"数组分配失败！";
17         exit(0);
18     }
19     //顺序选取两个有序区的较小元素，存储到t数组中，因为是递增排序
20     while(i <= mid && j <= high){
21         //较小的元素，存入temp临时数组中
22         if(List[i] <= List[j]){
23             temp[k++] = List[i++];
24         }else{
25             temp[k++] = List[j++];
26         }
27     }// end of while
28     //比完之后，假如第1个有序区仍有剩余，则直接全部复制到 temp 数组
29     while(i <= mid){
30         temp[k++] = List[i++];
31     }
32     //比完之后，假如第2个有序区还有剩余，则直接全部复制到 temp 数组
33     while(j <= high){
34         temp[k++] = List[j++];
35     }
36     //将排好序的序列，重存回到 list 中 low 到 high 区间
37     for(i = low, k = 0; i <= high; i++, k++){
38         List[i] = temp[k];
39     }
40     //delete [] 删除动态数组的内存
41     delete []temp;
42 }
43 
44 //递归实现二路归并排序（也就是分治法的思想）
45 void mergeSort(int List[], int low, int high)
46 {
47     //二路归并排序，分为二路
48     int mid = (low + high) / 2;
49     //终止条件，low >= high， 不是while，且不含等号，否则死循环
50     if(low < high)
51     {
52         //递归过程，二路归并排序递归过程
53         mergeSort(List, low, mid);
54         mergeSort(List, mid + 1, high);
55         //归并
56         merge(List, low, mid, high);
57     }
58 }
59 
60 int main(void)
61 {
62     int source[7] = {49, 38, 65, 97, 76, 13, 27};
63     
64     mergeSort(source, 0, 6);
65     
66     for (int i = 0; i < 7; i++) {
67         printf(" %d  ", source[i]);
68     }
69     
70     return 0;
71 }

 1 //非递归算法实现二路归并排序，length代表数组长度，即数组最大下标是 legth - 1
 2 void mergeSort(int List[],int length)
 3 {
 4     //回忆图解的过程，二路归并算法的流程，不同于递归，递归是先递归语句，然后归并函数，这样归并函数是倒序执行（和递归函数执行顺序相反）
 5     int size = 1;
 6     int low;
 7     int mid;
 8     int high;
 9     //size 是标记当前各个归并序列的high-low，从1，2，4，8，……，2*size
10     while(size <= length - 1)
11     {
12         //从第一个元素开始扫描，low代表第一个分割的序列的第一个元素
13         low = 0;
14         //当前的归并算法结束的条件
15         while(low + size <= length - 1)
16         {
17             //mid代表第一个分割的序列的最后一个元素
18             mid = low + size - 1;
19             //high 代表第二个分割的序列的最后一个元素
20             high = mid + size;
21             //判断一下：如果第二个序列个数不足size个
22             if(high > length - 1){
23                 //调整 high 为最后一个元素的下标即可
24                 high = length - 1;
25             }
26             //调用归并函数，进行分割的序列的分段排序
27             merge(List, low, mid, high);
28             //打印出每次归并的区间
29             cout << "low:" << low << " mid:" << mid << " high:" << high << endl;
30             //下一次归并时第一序列的第一个元素位置
31             low = high + 1;
32         }// end of while
33         //范围扩大一倍，二路归并的过程
34         size *= 2;
35     }// end of while
36 }

 1 def mergeSort(arr):
 2     import math
 3     if(len(arr)<2):
 4         return arr
 5     middle = math.floor(len(arr)/2)
 6     left, right = arr[0:middle], arr[middle:]
 7     return merge(mergeSort(left), mergeSort(right))
 8 
 9 def merge(left,right):
10     result = []
11     while left and right:
12         if left[0] <= right[0]:
13             result.append(left.pop(0));
14         else:
15             result.append(right.pop(0));
16     while left:
17         result.append(left.pop(0));
18     while right:
19         result.append(right.pop(0));
20     return result