算法第二弹，归并排序（merge sort）。语言：Javascript。 核心思想： 归并排序的思路还是比较简单的，话不多说，看图： divide阶段：每次把数组一分为二，循环直到每个分组只有一个元素为止。 merge阶段：每次比较两个待合并数组的第一个元素，将较小的元素添加到一个新创建的数组中。接着，被复制数组中的指针后移。再比较两个数组各自的第一个元素……循环直到两个数组中的一个被处理完为止。然后，把未处理完的数组剩下的元素复制到新数组的尾部。看不懂请移步下面的动图。 （下图来自维基百科） 代码 既然已经懂了归并排序的原理。那就可以开始敲代码了。 如果简单粗暴地把归并排序的思想转化为代码，那结果是这样的： 不过理想很丰满，现实很骨感。这种实现方法虽然做到了时间上的高效，但是空间上付出的代价时惨重的。想象一下，假设数组有 n 个元素，那么算法就要递归 log n 次，因为数组的元素个数是不会减少的，也就是每次要额外的 n 个空间来暂时存储划分好的元素。如果你计算的是一个比较大的数组，而你的计算机刚好又是那种内存比较小的……嗯，画面太美我不敢看。 一个好的解决方法是建立一个临时数组，每次递归时，交替使用临时数组和原数组来进行切片，合并，以达到节省空间的目的。（此时空间复杂度为 n）。 可以从两个方向来进行递归。 一个是自顶向下的归并排序（Top-Down)，代码如下。 代码可能有点难理解，看不懂的同学请拿出一张纸，创造一个数组，按着代码步骤一步一步将数组排序。实践出真理。 另一个是自底向上的归并排序（Bottom-Up），代码如下。 效率 空间复杂度 前面已经讲过，所以这里不再赘述。 时间复杂度 计算归并排序的键值比较次数，每做一步，都要进行一次比较，比较之后，两个数组中尚未处理的元素个数减 1 。 最坏情况下，无论哪个数组都不会为空，除非另外一个数组只剩下最后一个元素（也就是连个数组中的元素是按序交错存在的）。当每个数组有 k/2 个元素时，比较的次数为 k-1 （只有最后一个元素不用比较）。所以递归式为 最好情况下，其中一个数组的所有元素都小于另一个数组的最小元素，当每个数组有 k/2 个元素时，键值比较次数为 k/2 ，因此递归式为 ...