介绍

归并排序是一种分治策略的排序算法。它是一种比较特殊的排序算法，通过递归地先使每个子序列有序，再将两个有序的序列进行合并成一个有序的序列。

归并排序首先由著名的现代计算机之父 John_von_Neumann 在 1945 年发明，被用在了 EDVAC(一台美国早期电子计算机)，足足用墨水写了 23 页的排序程序。注：冯·诺依曼（John von Neumann，1903年12月28日-1957年2月8日），美籍匈牙利数学家、计算机科学家、物理学家，是20世纪最重要的数学家之一。

执行流程

我们先介绍两个有序的数组合并成一个有序数组的操作。

  • 先申请一个辅助数组，长度等于两个有序数组长度的和。
  • 从两个有序数组的第一位开始，比较两个元素，哪个数组的元素更小，那么该元素添加进辅助数组，然后该数组的元素变更为下一位，继续重复这个操作，直至数组没有元素。
  • 返回辅助数组。

时间复杂度

归并操作最坏的时间复杂度为：O(n)，其中 n 是较长数组的长度。

归并操作最好的时间复杂度为：O(n)，其中 n 是较短数组的长度。

代码实现


// 自顶向下归并排序，排序范围在 [begin,end) 的数组
func SortMerge(array []int, begin int, end int) {
	// 元素数量大于1时才进入递归
	if end-begin > 1 {

		// 将数组一分为二，分为 array[begin,mid) 和 array[mid,high)
		mid := begin + (end-begin+1)/2

		// 先将左边排序好
		SortMerge(array, begin, mid)

		// 再将右边排序好
		SortMerge(array, mid, end)

		// 两个有序数组进行合并
		merge(array, begin, mid, end)
	}
}

// 归并操作
func merge(array []int, begin int, mid int, end int) {
	// 申请额外的空间来合并两个有序数组，这两个数组是 array[begin,mid),array[mid,end)
	leftSize := mid - begin         // 左边数组的长度
	rightSize := end - mid          // 右边数组的长度
	newSize := leftSize + rightSize // 辅助数组的长度
	result := make([]int, 0, newSize)

	l, r := 0, 0
	for l < leftSize && r < rightSize {
		lValue := array[begin+l] // 左边数组的元素
		rValue := array[mid+r]   // 右边数组的元素
		// 小的元素先放进辅助数组里
		if lValue < rValue {
			result = append(result, lValue)
			l++
		} else {
			result = append(result, rValue)
			r++
		}
	}

	// 将剩下的元素追加到辅助数组后面
	result = append(result, array[begin+l:mid]...)
	result = append(result, array[mid+r:end]...)

	// 将辅助数组的元素复制回原数组，这样该辅助空间就可以被释放掉
	for i := 0; i < newSize; i++ {
		array[begin+i] = result[i]
	}
	return
}

测试

func TestSortMerge(t *testing.T) {
	list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	SortMerge(list,0,len(list))
	fmt.Println(list)

	list = []int{-1, 5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	SortMerge(list,0,len(list))
	fmt.Println(list)

	list = []int{-1, 11, 22, 33}
	SortMerge(list,0,len(list))
	fmt.Println(list)
}

测试结果

=== RUN   TestSortMerge
[1 3 4 5 6 6 6 8 9 14 25 49]
[-1 1 3 4 5 6 6 6 8 9 14 25 49]
[-1 11 22 33]
--- PASS: TestSortMerge (0.00s)
PASS