归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14；


c++ #include<iostream> using namespace std; // 将两组数归并为一组数 void merge(int *data, int start, int mid, int end, int *result) { int i, j, k; i = start; j = mid + 1; //避免重复比较data[mid] k = 0; while (i <= mid && j <= end) //数组data[start,mid]与数组(mid,end]均没有全部归入数组result中去 { if (data[i] <= data[j]) //如果data[i]小于等于data[j] result[k++] = data[i++]; //则将data[i]的值赋给result[k]，之后i,k各加一，表示后移一位 else result[k++] = data[j++]; //否则，将data[j]的值赋给result[k]，j,k各加一 } while (i <= mid) //表示数组data(mid,end]已经全部归入result数组中去了，而数组data[start,mid]还有剩余 result[k++] = data[i++]; //将数组data[start,mid]剩下的值，逐一归入数组result while (j <= end) //表示数组data[start,mid]已经全部归入到result数组中去了，而数组(mid,high]还有剩余 result[k++] = data[j++]; //将数组a[mid,high]剩下的值，逐一归入数组result for (i = 0; i < k; i++) //将归并后的数组的值逐一赋给数组data[start,end] data[start + i] = result[i]; //注意，应从data[start+i]开始赋值 } void merge_sort(int *data, int start, int end, int *result) { if (start < end) { int mid = start + (end-start) / 2;//避免溢出int merge_sort(data, start, mid, result); //对左边进行排序 merge_sort(data, mid + 1, end, result); //对右边进行排序 merge(data, start, mid, end, result); //把排序好的数据合并 } } void amalgamation(int *data1, int *data2, int *result) { for (int i = 0; i < 10; i++) result[i] = data1[i]; for (int i = 0; i < 10; i++) result[i + 10] = data2[i]; } int main() { int data1[10] = { 1,7,6,4,9,14,19,100,55,10 }; int data2[10] = { 2,6,8,99,45,63,102,556,10,41 }; int *result = new int[20]; int *result1 = new int[20]; // amalgamation 合并 amalgamation(data1, data2, result); for (int i = 0; i < 20; ++i) cout << result[i] << " "; cout << endl; merge_sort(result, 0, 19, result1); for (int i = 0; i < 20; ++i) cout << result[i] << " "; delete[]result; delete[]result1; return 0; }