归并排序（Merge Sort）是一种分治算法，它 将一个待排序的数组分成两个子数组，然后递归地对子数组进行排序 ，最后将两个有序的子数组 合并 成一个有序的数组。

例如，对于两个有序的子数组 A 和 B，我们借助一个 长度等于原数组 的临时数组 C，并为每个数组维护一个指针。通过指针的滑动比较，将 A 和 B 中较小的值填充到 C 中，完成一次合并（不同批次的归并过程，填充了临时数组 C 中的不同范围），最后再将数组 C 中的数据拷贝回原始数组，即可完成排序。

归并排序是经典的分治（divide-and-conquer）策略，它将问题分为一些小的问题，然后递归求解；而治的阶段则将分的阶段解得的各个答案修补到一起。

归并排序实现

归并排序

1
2
3
4
5
6
7
8

void mergeSort(int arr[], int tempArr[], int left, int right) {
    if (left < right) {
        int mid = left + ((right - left) >> 1);
        mergeSort(arr, tempArr, left, mid);        // 归
        mergeSort(arr, tempArr, mid + 1, right);   // 归
        merge(arr, tempArr, left, mid + 1, right); // 并
    }
}

并过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/* leftPos = start of left half, rightPos = start of right half, rightEnd = end of right half */
void merge(int arr[], int tempArr[], int leftPos, int rightPos, int rightEnd) {
    int leftEnd = rightPos - 1;
    int leftPtr = leftPos, rightPtr = rightPos, tempPtr = leftPos; // 三个指针

    // 两个有序的子数组 A 和 B，填充到临时数组 C 中
    while (leftPtr <= leftEnd && rightPtr <= rightEnd) {
        if (arr[leftPtr] <= arr[rightPtr]) {
            tempArr[tempPtr++] = arr[leftPtr++];
        } else {
            tempArr[tempPtr++] = arr[rightPtr++];
        }
    }
    while (leftPtr <= leftEnd) {
        tempArr[tempPtr++] = arr[leftPtr++];
    }
    while (rightPtr <= rightEnd) {
        tempArr[tempPtr++] = arr[rightPtr++];
    }

    // 将临时数组 C 拷贝回原始数组中
    for (int i = leftPos; i < rightEnd + 1; i++) {
        arr[i] = tempArr[i]; 
    }
}

如果在 merge() 的每次递归调用内部申请临时数组，那么在任一时刻就可能有 logN 个临时数组处在活动期，这对于小内存的机器是致命的；且频繁的分配空间并释放空间的时间占用也会很多。所以，最好在 mergeSort() 开始之前申请好临时数组，并在排序完成后释放。

归并排序测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int *tempArr = (int *)malloc(n * sizeof(int));

    mergeSort(arr, tempArr, 0, n - 1);

    printf("After mergeSort: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n"); // After mergeSort: 1 1 2 3 3 4 5 5 5 6 9
    free(tempArr);

    return 0;
}

归并排序分析

时空复杂度

• 最坏时间复杂度：O(NlogN)；
• 空间复杂度：O(N)，在「并」的过程中需要一个临时数组。

时间复杂度分析

假设 $N$ 是 $2$ 的幂，从而我们总可以将原数组（假设长度为 $2^{k}$）分裂成大小相同的两部分（大小为 $2^{k-1}$）。

• 对于 $N=1$，归并排序所用时间是常数，记为 $T(1) = 1$；
• 否则，对 $N$ 个数归并排序的用时，等于完成两个大小为 $\frac{N}{2}$ 的递归排序所用的时间，再加上合并的时间（它是线性的），记为 $T(N) = 2 \times T(\frac{N}{2}) + N$。

求解 $T(N)$ 方法一，用 $N$ 去除递推关系式的两边：

因为 $T(N) = 2 \times T(N/2) + N$，两边同时除以 $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$

$\frac{T(N/4)}{N/4} = \frac{T(N/8)}{N/8} + 1$

$\frac{T(N/8)}{N/8} = \frac{T(N/16)}{N/16} + 1$

$\frac{T(N/2^{k-1})}{N/2^{k-1}} = \frac{T(1)}{1} + 1$

上面系列等式的左边之和等于右边之和，化简有：$\frac{T(N)}{N} = \frac{T(1)}{1} + logN$

因此，$T(N) = N \times log(N) + N = O(N \times logN)$

求解 $T(N)$ 方法二，在右边连续地代入递归关系：

$T(N) = 2 \times T(\frac{N}{2}) + N$
$= 2 \times (2 \times T(\frac{N}{4}) + \frac{N}{2}) + N = 2^2 \times T(\frac{N}{2^2}) + 2N$
$= 2^2 \times (2 \times T(\frac{N}{8}) + \frac{N}{4}) + 2N = 2^3 \times T(\frac{N}{2^3}) + 3N$
$= ...$
$= 2^k \times T(\frac{N}{2^k}) + k \times N$

利用 $k = logN$，可以得到 $T(N) = N \times T(1) + log(N) \times N = O(N \times logN)$

排序效率分析

虽然归并排序的运行时间是 $O(N \times logN)$，但它很难用于主存排序，主要问题在于：

1. 合并两个排序的表需要线性附加内存；
2. 在整个算法中还要花费时间将数据拷贝到临时数组，再拷贝回原始数组的一些附加工作，其结果严重放慢了排序的速度。

参考资料：数据结构与算法分析：C 语言描述（第 2 版）