Go-归并排序

func merge(list []int, left, mid, right int) {
  lLen := mid - left + 1
  rLen := right - mid
  length := lLen + rLen
  result := make([]int, length)
  // 左边起始位置：left 右边起始位置mid + 1
  // 真实位置： 起始位置 + 索引位置
  for idx, lIdx, rIdx := 0, 0, 0; idx < length; idx++ {
    if lIdx >= lLen {
      result[idx] = list[mid+1+rIdx]
      rIdx++
    } else if rIdx >= rLen {
      result[idx] = list[left+lIdx]
      lIdx++
    } else if list[left+lIdx] > list[mid+1+rIdx] {
      result[idx] = list[mid+1+rIdx]
      rIdx++
    } else {
      result[idx] = list[left+lIdx]
      lIdx++
    }
  }
  // 写回去
  for idx := 0; idx < length; idx++ {
    list[left+idx] = result[idx]
  }
}

func MergeSort(list []int, left, right int) {
  if left < right {
    mid := (left + right) / 2
    MergeSort(list, left, mid)
    MergeSort(list, mid+1, right)
    merge(list, left, mid, right)
  }
}

func main() {
  list := []int{8, 4, 8, 2, 9, 10, -3, 3, 20, 15, -1}
  function.MergeSort(list, 0, len(list)-1)
  fmt.Println(list)
}