算法-归并排序.md

归并排序

分治法

分治法是将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：

1. 分解：分解原问题为若干子问题，这些子问题时原问题的规模较小的实例。
2. 解决：解决这些子问题，递归地求解各子问题。若子问题的规模足够小，则直接求解。
3. 合并：合并这些子问题的解成原问题的解。

算法

归并排序算法完全遵循分治模式，直观上其操作如下：

1. 分解：分解待排序的 n 个元素的序列成各具 n/2 个元素的两个子序列。
2. 解决：使用归并排序递归地排序两个子序列。
3. 合并：合并两个已排序的子序列以产生已排序的答案。

实现

分解

过程 MERGE-SORT(A,p,r) 排序子数组 A[p..r] 中的元素。若 p>=r ,则该子数组最多有一个元素，所以已经排好序。

否则，分解步骤简单地计算一个下标 q,将 A[p..r] 分成两个子数组 A[p..q] 和 A[q+1..r]

过程 MERGE-SORT 目的在于将数组 A 递归地对半分解成两个子序列，直到子序列分成一个元素为止。

分解的过程如下图所示:

伪代码如下所示：

解决

在归并排序中，解决的含义是递归地排序两个子序列，在实现上实际上是在递归分解后执行合并操作的一个入口，也就是在伪代码中的：

//分解
MERGE-SORT(A,p,q)
//分解
MERGE-SORT(A,q+1,r)
//解决
MERGE(A,p,q,r)

合并

归并排序调用一个过程 MERGE(A,p,q,r) 来完成合并，其中 A 是一个数组，p,q,r 是数组下标，满足 p<=q<r。

该过程假设子数组 A[p..q] 和 A[q+1..r] 都已排好序，它合并两个子数组形成单一的已排好序的子数组并代替当前的子数组 A[p..r]

复杂度

当一个算法包含对其自身的递归调用时，我们可以用递归方程式活递归式来描述其运行时间，该方程式根据在较小输入上的运行时间来描述在规模为 n 的问题上的总运行时间。

分治算法运行时间的递归式来自基本模式的三个步骤。为了求解一个规模为 n/b 的子问题，需要 T(n/b) 的时间，所以需要 aT(n/b)的时间来求解 a 个子问题。

分解问题成子问题需要时间 D(n),合并子问题的解成原问题的解需要时间 C(n)，相加的和是 n 的一个线性函数，即 O(n)，于是归并排序的最坏情况运行时间的递归式为：

由此递归式可以进一步分析得出递归树：

为了计算递归式表示的总代价，我们只要把树中各层的代价加起来，递归树具有 lgn+1 层，每层的代价均为 cn，所以总的代价为 cn(lgn+1) = cnlgn + cn。

忽略低阶项和常量，归并排序的时间复杂度为 O(nlgn)

因为归并排序在 MERGE 过程中会新建数组来存放临时数组，临时数组大小最差的情况和数组一样大，所以归并排序的空间复杂度为 O(n)

go 实现

go 的许多特性可以让归并排序的实现更加的简单，以下的实现中就用到了 go 的 slice 特性，来简化数组的分割工作。

数组的分割操作可以通过 r[:mid]，r[mid:] 的语法来实现，在 merge 方法中，也用到了 append 语法来快速添加排序结果集。

type MergeSort struct {
	Value []int
}

func (m *MergeSort) Sort() ([]int, error) {
	m.Value = mergeSort(m.Value)
	return m.Value, nil
}

func mergeSort(r []int) []int {
	len := len(r)
	if len <= 1 {
		return r
	}
	mid := len / 2
	left := mergeSort(r[:mid])
	right := mergeSort(r[mid:])
	return merge(left, right)
}

func merge(left, right []int) (result []int) {
	l, r := 0, 0
	for l < len(left) && r < len(right) {
		if left[l] < right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	result = append(result, left[l:]...)
	result = append(result, right[r:]...)
	return result
}