归并排序

排序

说明

递归排序两半再合并；稳定，时间 O(n log n)、额外空间 O(n)。

分析

递归把数组分成两半，分别排序后通过比较两边当前元素完成合并。合并时优先取左侧相等元素可保持稳定性。

图解推演

[3,1,2] 拆为 [3] 与 [1,2]，后者继续拆到单元素再合并。合并时两边各维护一个游标，每次取较小值；一边用尽就追加另一边。相等时先取左侧，是稳定性的来源，而不是“递归”本身保证稳定。

查看图表代码

适用前提与边界

每层总工作为 O(n)，层数为 O(log n)；代价是需要额外的合并空间。

示例输入与调用

fmt.Println(MergeSort([]int{3, 1, 2}))

运行输出

[1 2 3]

完整 Go 示例

package main

import "fmt"

func MergeSort(a []int) []int {
	if len(a) < 2 {
		return append([]int(nil), a...)
	}
	m := len(a) / 2
	l, r := MergeSort(a[:m]), MergeSort(a[m:])
	out := make([]int, 0, len(a))
	for len(l) > 0 && len(r) > 0 {
		if l[0] <= r[0] {
			out = append(out, l[0])
			l = l[1:]
		} else {
			out = append(out, r[0])
			r = r[1:]
		}
	}
	return append(append(out, l...), r...)
}

func main() {
	fmt.Println(MergeSort([]int{3, 1, 2}))
}