归并排序算法

是分治法（divide and conquer)的思想：就是把一个大问题分解成相似的小问题，再用小问题的解构造大问题的解。

分治法基本都是用递归来实现的。递归是一种编程技巧，分治法是一种解决问题的思想。

分治法分为三步：

【分】：大问题分解成小问题

【治】：用同样的方法解决小问题

【合】：用小问题的解构造大问题的解

例如归并排序：

「分」：把一个数组拆成两个；

「治」：用归并排序去排这两个小数组；

「合」：把两个排好序的小数组合并成大数组。

这里还有个问题，就是什么时候能够解决小问题了？

答：当只剩一个元素的时候，直接返回就好了，分解不了了。这就是递归的 base case，是要直接给出答案的。

图解 源码 测试

原文连接