Day 11：合并排序(mergesort)

合并排序(merge sort 或 mergesort)是另一种采用分治法的排序演算法。
它的步骤是：

1. 分割：用递回的方式，将长度为n的数列分成两半，直到子数列长度为1。
2. 合并：将上一步的子数列合并成为一个有序数列。

举例来说，这是对七个元素的数列进行合并排序的图：

图片来源：维基百科

图的上半是反覆将原数列分成两半，直到分割成七个长度为一的子数列。这部分递回想法跟上一回快速排序很接近，就是当数列被分解到最小单位时，可以当作已经排序完成。

接下来合并的步骤，就是依序将两个相邻子数列的元素进行比较，并合并在一起。举例来说，(27, 38)与(3, 43)两个子数列的合并，就是27与3比较，接着27与43比较，接着38与43...每次比较都把较小的数字加入新阵列。最终所有的子数列合并即为排序好的数列。

执行时间

合并排序先是反覆将数列分成两半，所以这部分执行时间是我们熟悉的O(log n)。而後面每一层的合并则都要操作所有n个元素一遍，所以两者相乘，合并排序的操作时间为O(n log n)。而在最佳情况，合并排序的执行时间也是Ω(n log n)，即便是操作有序数列，合并排序也是进行同样的步骤。

快速排序 vs. 合并排序

看到这里，眼尖的人会有这样的疑问：如果上一回的快速排序平均执行时间才O(n log n)，最坏会是O(n²)，可是合并排序最坏就是O(n log n)，那那那，当然是用合并排序啊？

事实上，快速排序达到O(n log n)的比例很高，且实务中常常比同为O(n log n)的合并排序还有效率，所以仍然是许多排序任务的首选。而合并排序对於操作某些资料结构特别有效，例如只能循序存取(sequential access，只能以特定顺序取值，无法随机存取)的资料结构。

另一个快速排序比合并排序更有优势的地方在於空间需求较少。快速排序进行的是原地(in-place)操作，因为是透过反覆交换元素完成排序，主要在原输入阵列上操作即可，只需要少量额外记忆体空间。而通常合并排序在每一阶段的合并都需要新的空间来储存合并的阵列，空间需求较高。

排序演算法操作比较

从一开始的选择排序到现在的合并排序，讨论了很多排序方式。以下影片是一些排序演算法的比较，用视觉化的方式表现各个演算法在输入不同(例如随机、排序完全颠倒、几乎已排序好的情况)时的表现。