# 归并排序 ## 分治法 分治法是将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。 分治模式在每层递归时都有三个步骤： 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 递归地对半分解成两个子序列，直到子序列分成一个元素为止。 分解的过程如下图所示: ![序列](https://cnymw.github.io/GolangStudy/docs/img/�