Question

排序算法（二）:递归排序之归并排序

Answer 1

    递归就是函数调用本身，和高中数学的数学归纳法类似。当在求一个数组的第n项的时候，有两种方式，第一种就是根据各种公式，求通项公式，第二种，就是数学归纳法，发现数据项前后两项的规律。可以这么说，递归只要知道开始的特殊情况，知道过程是如何展开的。（递推：相反使用一个循环来实现，但有的时候递推有一定难度，不过可以使用栈来实现消除递归，这么说，一些编译器都是用栈来实现递归的）

    归并排序的原理是，合并两个有序的数组。两个有序数的合并相对较为简单， 通常遍历一遍就可以合并。因此只要保证两个数组是有序，然后进行一次合并，就得到一个有序数组。那么，上述的过程已经发现了，假设要对一个数组进行排序，那么可以将其一分为二，得到两个数组，那么如何保证这两个数组有序的。这里已经很明显的，问题又回到开头，也就是递归（调用函数本身）。递归不能只是关注过程，也要关注（边界问题），不然可能会陷入死循环，甚至坐标越界。现在的（边界）就是，何时，数组不可再分？很显然，就是也就是数组小于二。换而言之，就是数组大于一是调用函数本身。