前言
上一篇文章写了一个自顶向下的归并排序，把一个完整的数组不断二分，然后再合并。其实换一种思路：把数组中相邻的N个元素看成是已经二分好了的，直接进行合并，就省掉了二分那一步骤
C++实现:
?templatevoidmergeSortButton2Top(T arr[], intn) {for(intsize = 1; size <= n; size += size) {for(inti = 0; i+size < n; i+=2*size) //对[i,i+size-1]和[i+size,i+2*size-1]进行归并__merge(arr, i, i + size - 1, min(i + size + size - 1,n-1));// arr left mid right 如果i+2*size>n了，越界了，就取n-1}}templatevoid__merge(T arr[], intleft, intmid, intright) { //将arr[left,mid] 和 arr[mid+1,right] 两部分进行归并T *tmp=newT[right-left+1];for(inti = left; i <= right; i++)tmp[i - left] = arr[i]; //先把arr（需要合并的左右片段） 复制给tmpinti = left, j = mid + 1; // i 做为左半部分的指针 j作为右半部分的指针for(intk = left; k <= right; k++) {if(i > mid) { // 左半部分 已经合入完了，将右半部分剩下的 全部合入arr[k] = tmp[j - left];j++;}elseif(j > right) { // 右半部分 已经合入完了，将左半部分剩下的 全部合入arr[k] = tmp[i - left];i++;}elseif(tmp[i - left] < tmp[j - left]) {arr[k] = tmp[i - left];i++;}else{arr[k] = tmp[j - left];j++;}}delete[] tmp;}intmain() {intarr[9] = { 1,5,6,78,12,5,1,12,54 };mergeSortButton2Top(arr,9);for(inti = 0; i < 9; i++) {cout << arr[i]<<" ";}return0;} GoLang实现:
?func mergeSortButton2Top(arr [] int) {var lenth int= len(arr)forsize := 1; size <= lenth; size += size {fori := 0; i+size < lenth; i += 2 * size { //对[i,i+size-1]和[i+size,i+2*size-1]进行归并merge(arr, i, i+size-1, int(math.Min(float64(i+2*size-1), float64(lenth-1))))// arr left mid right 如果i+2*size>n了，越界了，就取n-1}}}func merge(arr []int, left, mid, right int) {// 将要合并的部分做个拷贝var tmp []int= make([]int, right-left+1)fori, j := left, 0; i <= right; i++ {tmp[j] = arr[i]j++}// i做为左半部分的指针 j作为右半部分的指针var i, j int= left, mid+1fork := left; k <= right; k++ {ifi > mid { // 左半部分 已经合入完了，将右半部分剩下的 全部合入arr[k] = tmp[j-left]j++} elseifj > right { // 右半部分 已经合入完了，将左半部分剩下的 全部合入arr[k] = tmp[i-left]i++} elseiftmp[i-left] > tmp[j-left] {arr[k] = tmp[j-left]j++} else{arr[k] = tmp[i-left]i++}}}用golang对两种归并排序进行计时，观察性能：
?func createRandomArray(count int) []int{rand.Seed(time.Now().UnixNano())var arr [] int= make([]int, 0)fori := 0; i < count; i++ {arr = append(arr, rand.Intn(100))}returnarr}func main() {count := 10000arr := createRandomArray(count)var arr2 []int= make([]int, count)copy(arr2, arr)start := time.Now()mergeSort(arr, 0, len(arr)-1)fmt.Println("自顶向下归并排序 用时：", time.Since(start))start = time.Now()mergeSortButton2Top(arr2)fmt.Println("自底向上归并排序 用时：", time.Since(start))}//输出：//自顶向下归并排序 用时： 4.997ms//自底向上归并排序 用时： 3.9987ms因为自底向上少了二分那个步骤，性能要优于自顶向下的归并排序
总结
原文链接：https://www.jianshu.com/p/57e432a7676e