先说一下，这个归并排序是我自己的一些想法。简单地浏览了一下书本（《算法：C语言实现》（第三版）），实现方法并不一致。
但是这个算法我测试了一下，还行。
归并排序：分治法的思路。把一个待排序的数组（arr）分成两半（arrA和arrB）进行归并排序。在归并排序的过程中，arrA再分成两半……这个过程直到子数组无可再分。然后就回溯（应该是这么用这个名词），分别这些一对一对的细小的子数组进行插入排序……当这个过程回溯到arr的时候，由于arrA和arrB都已经是有序的子数组了，对arr的插入排序的工作量就相当小了。
1 void 2 InsertSort(int arr[], int left, int right) 3 { 4 for (int i = left+1; i <= right; i++) { 5 int tmp = arr[i]; 6 for (int j = i-1; j >= 0 && arr[j] > tmp; j--) { 7 arr[j+1] = arr[j]; 8 arr[j] = tmp; 9 } 10 } 11 } 12 13 void 14 MergeSort(int arr[], int left, int right) 15 { 16 if (left == right) { 17 return; 18 } 19 20 int middle = (left + right) / 2; 21 22 MergeSort(arr, left, middle); 23 MergeSort(arr, middle+1, right); 24 25 InsertSort(arr, left, right); 26 }
原文：http://www.cnblogs.com/nipan/p/4052815.html