merge-sort

归并排序

多线程可用。

• 稳定性

  稳定（合并时先插入前方元素）

• 复杂度

  • 时间复杂度

    非常稳定，永远 O(n(log n))

  • 空间复杂度

    O(n) 空间不用 n 都是在原数组上进行操作，会降低性能。 原方法直接把两个数组过一遍，merge 进去就够了，在原数组上进行排序，又要走一整套（或者半套算法），时间复杂度绝对高于 O(n)。

• 原理

  把整个数组全部拆开成二叉树形，然后分别排序，不停合并，排序，最终就是一个有序的数组了。