6. 进阶排序算法——归并排序（golang）

归并排序

归并排序的思想核心

分组合并

分组合并

如此重复，直至得到一个有序序列。

递归版本代码实现

func MergeSort(arr []int) []int {

	// 数组长度
	length := len(arr)

	// 数组为空或者数组只有一个元素
	if length <= 1 {
		return arr
	}

	// 中间点
	mid := length / 2

	// 递归
	leftArr := MergeSort(arr[:mid])
	rightArr := MergeSort(arr[mid:])

	// 归并
	return merge(leftArr, rightArr)
}

func merge(left []int, right []int) []int {

	// 最终结果
	var result []int
	
	for len(left) != 0 && len(right) != 0 {
	
		// 左边小于右边
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]
		// 左边大于右边
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
	
	// 把没有结束的归并过来
	for len(left) != 0 {
		result = append(result, left[0])
		left = left[1:]
	}
	for len(right) != 0 {
		result = append(result, right[0])
		right = right[1:]
	}

	return result
}

迭代版本代码实现

时间复杂度

归并排序的时间复杂度为O(nlogn)。

稳定性

归并排序在合并的时候都需要进行两两比较，所以它是一种稳定排序算法。