2.2.2自顶向下的归并排序

实现原理

采用分治思想，自顶向下不断对数组进行归并排序。

效率分析

对于长度为N的数组，需要比较NlogN次。

代码实现

func sort(a []int) {
  aux = make([]int, len(a))
  _sort(a, 0, len(a) - 1)
}
func _sort(a []int, lo, hi int) {
  if hi <= lo {
    return
  }
  mid := lo + (hi - lo) / 2
  _sort(a, lo, mid)
  _sort(a, mid + 1, hi)
  merge(a, lo, mid, hi)
}

优化方法

1. 对小规模子数组使用插入排序

处理小规模的数组（长度小于15）时，使用插入排序。

1. 测试数组是否已经有序

如果a[mid] 小于等于 a[mid+1] 就可以认为数组已经是有序的。