一、简介

思路：主要利用分而治之的策略，把待排序的数组逐渐分解，针对分解后数组进行排序，最终合并排序的多个小数组即可。具体如下图：

二、实现

func Sort(data []int) []int {
   dataLen := len(data)
   if dataLen == 0 {
      return data
   }

   if dataLen == 1 {
      return data
   }

   if dataLen == 2 {
      if data[0] > data[1] {
         temp := data[0]
         data[0] = data[1]
         data[1] = temp
      }

      return data
   }

   // 拆分
   middle := dataLen / 2
   leftData := Sort(data[:middle])
   rightData := Sort(data[middle:])

   // 合并
   return Merge(leftData, rightData)
}

// 合并
func Merge(data1, data2 []int) []int {
   data1Len := len(data1)
   data2Len := len(data2)

   data := make([]int, data1Len+data2Len)
   i := 0
   index1 := 0
   index2 := 0
   for {
      if index1 > data1Len && index2 > data2Len {
         break
      }

      if index1 >= data1Len {
         if index2 >= data2Len {
            break
         }

         data[i] = data2[index2]
         i++
         index2++
         continue
      } else {
         if index2 >= data2Len || data1[index1] <= data2[index2] {
            data[i] = data1[index1]
            i++
            index1++

            continue
         }

         data[i] = data2[index2]
         i++
         index2++
      }
   }

   return data
}

三、性能分析

1、稳定的排序

2、时间复杂度 n * logn