2.2.3 自底向上的归并排序

实现原理

先进行两两排序（将每个元素想象成大小为1的数组），再四四归并… 直到最后。

效率分析

时间复杂度依然是Nlog，只不过不需要递归减少压栈的操作。

代码实现

func sort(a []int) {
  aux = make([]int, len(a))
  N := len(a)
  for sz := 1; sz < N; sz = sz + sz {
    for lo := 0; lo < N - sz; lo += sz {
      merge(a, lo, lo + sz - 1, min(lo + sz + sz -1, N - 1))
    }
  }
}