.归并排序

执行流程

1. 不断地将当前序列平均分割成2个子序列 (分割)
   直到不能再分割(序列中只剩1个元素)
2. 不断地将2个子序列合并成一个有序序列 (合并)
   直到最终只剩下1个有序序列

package mysort

type MergeSort struct {
   leftArray []int
   Sort
}

func (this *MergeSort) SortFunc() {
   this.leftArray = make([]int, len(this.Array)>>1)
   this.sort(0, len(this.Array))
}

// [begin,end)
func (this *MergeSort) sort(begin, end int) {
   if end-begin < 2 {
      return
   }

   mid := begin + ((end - begin)>> 1)
   this.sort(begin, mid)
   this.sort(mid, end)
   this.merge(begin, mid, end)

}

// 将 【begin mid) 和 [mid end)
func (this *MergeSort) merge(begin, mid, end int) {
   li, le := 0, mid-begin
   ri, re := mid, end
   ai := begin
   // 备份左边数组  将 [begin,mid) 备份出来
   for i := li; i < le; i++ {
      this.leftArray[i] = this.Array[begin+i]
   }
   //如果左边还没有结束，如果右边结束的话，那么就不用管任何事情了
   for li < le {
      if ri < re && this.ComWithValue(this.Array[ri], this.leftArray[li]) < 0 {
         this.Array[ai] = this.Array[ri]
         ai++
         ri++
      } else {
         this.Array[ai] = this.leftArray[li]
         ai++
         li++
      }
   }
}
// 排序数组大小 1000000 排序方法 堆排序 排序比较次数 18388630 排序交换次数 999999 耗时 191247000
//排序数组大小 1000000 排序方法 归并排序 排序比较次数 18670630 排序交换次数 0 耗时 135949000