定义
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 O(n\log n)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
操作
递归法（Top-down） 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 设定两个指针，最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 迭代法（Bottom-up） 原理如下（假设序列共有 n个元素）：
将序列每相邻两个数字进行归并操作，形成 (n/2)个序列，排序后每个序列包含两/一个元素 若此时序列数不是1个则将上述序列再次归并，形成(n/4)个序列，每个序列包含四/三个元素 重复步骤2，直到所有元素排序完毕，即序列数为1
实现
// merge Sort
package main
import (
"fmt"
)
func mergeSort(c []int) []int {
var n = len(c)
if n < 2 {
return c
}
var m = n / 2
var lCol = c[:m]
var lSize = len(lCol)
if lSize >= 2 {
lCol = mergeSort(lCol)
}
var rCol = c[m:]
var rSize = len(rCol)
if rSize >= 2 {
rCol = mergeSort(rCol)
}
var tmp = make([]int, 0)
var i, j = 0, 0
for i < lSize && j < rSize {
if lCol[i] < rCol[j] {
tmp = append(tmp, lCol[i])
i++
} else {
tmp = append(tmp, rCol[j])
j++
}
}
if i < lSize {
tmp = append(tmp, lCol[i:]...)
}
if j < rSize {
tmp = append(tmp, rCol[j:]...)
}
return tmp
}
测试
//test
func main() {
var b = []int{35, 9, 8, 6, 20, 7, 4, 3, 2, 1}
fmt.Println(mergeSort(b))
}
