归并排序

(图片来自 归并排序 - 十大经典排序算法

思路

我们可以利用分治法(divide and conquer),每次递归都只排序待排序数组的一部分,然后慢慢归并。好处是每次都不需要跟剩余所有数比较一遍,而是跟剩余的数中的较小的数比较,因此平均情况会比 $O(n^2)$ 快。其算法步骤如下:

  1. 申请空间 C,其大小为两个已排序序列(假设为 AB)的大小之和,用来存放合并后的序列。
  2. 使用两个指针分别指向 AB 的开头。
  3. 比较两个指针指向的元素,选择较小的元素放入 C,移动对应序列的指针到下一位置。
  4. 重复第 3 步直到某个指针达到所在序列的末尾。
  5. 将另一序列剩余所有元素复制到 C 的末尾。

分析

  • 平均、最好、最坏时间复杂度都为 $O(n \log n)$,其中的 $n$ 是每次归并都需要比较所有的数字,而 $\log n$ 则是需要归并的次数。
  • 空间复杂度为 $O(n)$,属于 Out-place 排序。
  • 算法稳定。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。