归并排序

我们在希尔排序中也可以看到，将待排序数组分割为若干个小数组来优化平方时间复杂度的算法是非常有效的：单元问题的规模变为原$1/n$，处理这个单元问题的时间则变为原$1/{n^2}$，而分割后存在着$n$个单元问题，综合下来它将分割后的问题处理时间缩小了$1/n$。而我们往往要引入一个额外的过程来将分割后的答案变成整体的答案，而这个过程多数情况下是$O(N)$的。
因此我们现在要换一个角度来实现上述的思想。我们把数组每次对半细分直到每一个单元最多只剩2个元素。然后我们将这两个元素排成正序，随后每两组合并为一个正序序列，一直进行直到合并完成。
对于这个算法，使用递归将是很好的想法：

def mergeSort(arr):
    _mergeSort(arr, 0, len(arr) - 1)
    return arr

def _mergeSort(arr, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    _mergeSort(arr, left, mid)
    _mergeSort(arr, mid + 1, right)

    tempArr = []
    leftPoint = left
    rightPoint = mid + 1
    while leftPoint <= mid or rightPoint <= right:
        if leftPoint > mid:
            tempArr.append(arr[rightPoint])
            rightPoint += 1
        elif rightPoint > right:
            tempArr.append(arr[leftPoint])
            leftPoint += 1
        elif arr[leftPoint] > arr[rightPoint]:
            tempArr.append(arr[rightPoint])
            rightPoint += 1
        else:
            tempArr.append(arr[leftPoint])
            leftPoint += 1
    for i in range(left, right + 1):
        arr[i] = tempArr[i - left]

讨论这个算法的时间复杂度多少有点麻烦，但是，不同于希尔排序的是，至少我们基于我们目前的数学知识来说还可以做：
我们考虑在一次迭代中我们所作的事：对于长度为n的输入，我们将一个规模为$n$的问题转化为两个规模为$n/2$的问题并附带了一个时间开销为$n$的附加过程，我们以$T(·)$表示问题 $·$ 的时间：我们的算法时间的递推式可以描述如下：

$T(n)=2T(n/2)+n$
$T(1)=1$

简单的中学数学(等式左右同除n)

$\frac{T(n)}{n}=\frac{T(n/2)}{n/2}+1$
$\frac{T(n/2)}{n/2}=\frac{T(n/4)}{n/4}+1$
$\dots$
$\frac{T(2)}{2}=\frac{T(1)}{1}+1$

一共有$\log_2 n$个等式，全加起来：

$\frac{T(n)}{n}=\frac{T(1)}{1}+\log_2 n$

则

$T(n)=n\log_2 n+n=O(n\log n)$

故归并排序是线性指数时间级别的。它的额外空间是$O(n)$，来源于合并过程中的辅助数组，但是这个额外空间可以被繁琐地优化至$O(1)$。
在这个实现中，由于判断条件elif arr[leftPoint] > arr[rightPoint]: ... else:，对于相同的键，优先放前边的元素，排序是稳定的。