小撒是一只好学的小鸭子，这天，小撒在学习算法
分治法
分治法（divide-and-conquer）是一种算法设计策略。使用分治法的算法在每一层迭代有3个步骤：
- 分解（divide）：将原问题分解成一系列子问题
- 解决（conquer）：递归解决子问题；在子问题足够小时，直接解决子问题
- 合并（combine）：将子问题的结果合并为原问题的解
合并排序
合并排序（merge sort）便是使用了分治的策略。
如果我们有两个已经排序好的数组，要得到两者合并后的排序数组，我们只需反复比较两个数组头部（最小）的元素，将更小的取出并放入结果数组：
合并排序图示
我们可以不断的将规模为n的问题分解为规模为n / 2的问题，直至n/2 <= 1：
合并排序的时间复杂度
递归树（recursion tree）每向下一层，规模为n的问题T(n)被分解为两个T(n/2)的问题，因此树的总高度为ln(n)/ln(2)。
而合并两个T(n/2)，则共需要n次比较并取出较小值，因此每层的总操作数为n，由此得到合并排序的时间复杂度为θ(n * log(n))。
代码示例（js）
const merge = (arr, start, mid, end) => {
const arr1 = arr.slice(start, mid + 1)
const arr2 = arr.slice(mid + 1, end + 1)
while (end >= start) {
if (arr2.length === 0) {
arr[start] = arr1.shift()
} else if (arr1[0] < arr2[0]) {
arr[start] = arr1.shift()
} else {
arr[start] = arr2.shift()
}
start++
}
}
const mergeSort = (arr, start, end) => {
if (end > start) {
const mid = Math.floor((end + start) / 2)
mergeSort(arr, start, mid)
mergeSort(arr, mid + 1, end)
merge(arr, start, mid, end)
}
}
小结
合并排序使用了分治的算法策略，相比插入排序等算法大大提高了时间复杂度，但也引入了O(n)的空间成本。
