实现原理

创建一个适当大小的数组，然后将两个数组中的元素一个个从大到小依次放入其中。

效率分析

只需要遍历一遍，时间复杂度为N

代码实现

  1. var aux []int
  3. func less(v, w int) bool {
  4.   return v < w
  5. }
  7. // 将 a[lo, mid] 和 a[mid+1, hi]进行归并
  8. func merge(a []int, lo, mid, hi int) {
  9.   i, j := lo, mid + 1
  11.   // copy array
  12.   for k := lo; k <= hi; k++ {
  13.     aux[k] = a[k]
  14.   }
  16.   for k := lo; k <= hi; k++ {
  17.     if i > mid {
  18.       a[k] = aux[j]
  19.       j++
  20.     } else if j > hi {
  21.       a[k] = aux[i]
  22.       i++
  23.     } else if less(aux[j], aux[i]) {
  24.       a[k] = aux[j]
  25.       j++
  26.     } else {
  27.       a[k] = aux[i]
  28.       i++
  29.     }
  30.   }
  31. }