基本思想
从中间将数据分为前后两部分，然后分别排序，最后进行合并。
算法分析
时间复杂度
最好、最坏、平均都是O(nlog2n)
T(1)=c
T(n)=2*T(n/2)+n
=2*(2*T(n/4)+n/2)+n
···
=2k*T(n/2k)+k*n
当2k=1时，k=log2n，所以T(n)=c*n+nlog2n
空间复杂度
O(n)
稳定性
合并时先放前边的元素即可保证数据稳定性.
参考代码
//归并
func mergeSortASC(value common.Value) {
len := value.Len()
if len < 2 {
return
}
mid := len / 2
lValue := value[:mid]
rValue := value[mid:]
mergeSortASC(lValue)
mergeSortASC(rValue)
tempValue := common.NewValueNil(len)
i, j := 0, 0
for i < lValue.Len() && j < rValue.Len() {
if lValue[i] <= rValue[j] {
tempValue = append(tempValue, lValue[i])
i++
} else {
tempValue = append(tempValue, rValue[j])
j++
}
}
if i < lValue.Len() {
tempValue = append(tempValue, lValue[i:]...)
}
if j < rValue.Len() {
tempValue = append(tempValue, rValue[j:]...)
}
for i = 0; i < value.Len(); i++ {
value[i] = tempValue[i]
}
}
