归并排序

定义与基本思想

归并排序（Merge Sort）是一种分治法思想的高效排序算法。其基本思想是：将序列递归地分成两半，分别排序后再合并成一个有序序列。

归并排序演示

84571362

当前归并区间: [0, 1]

下一步

算法描述

1. 将序列递归分成两半，直到每个子序列只有一个元素
2. 两两合并子序列，合并时按顺序归并成有序序列
3. 重复合并直到全部有序

伪代码如下：

function mergeSort(A, left, right):
    if left < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid+1, right)
        merge(A, left, mid, right)

function merge(A, left, mid, right):
    创建临时数组tmp
    i = left, j = mid+1, k = 0
    while i <= mid and j <= right:
        if A[i] <= A[j]:
            tmp[k++] = A[i++]
        else:
            tmp[k++] = A[j++]
    复制剩余元素到tmp
    将tmp复制回A[left..right]

代码实现

// 合并两个有序区间 A[left..mid] 和 A[mid+1..right]
void Merge(int A[], int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = A[left + i];
    for (int j = 0; j < n2; j++) R[j] = A[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) A[k++] = L[i++];
        else A[k++] = R[j++];
    }
    while (i < n1) A[k++] = L[i++];  // 复制剩余
    while (j < n2) A[k++] = R[j++];
}

void MergeSort(int A[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        MergeSort(A, left, mid);         // 左半排序
        MergeSort(A, mid + 1, right);    // 右半排序
        Merge(A, left, mid, right);      // 合并
    }
}

自然归并排序

与标准归并（固定对半划分）不同，自然归并先扫描找出序列中已有的有序子段（天然有序的”run”），直接对这些子段进行归并，减少归并趟数，尤其适合数据局部有序的场景。

时间复杂度分析

• 最好/最坏/平均情况：$O(n\log n)$
• 空间复杂度：$O(n)$
• 稳定性：稳定排序

习题

习题 1

对数组 $A = [8, 4, 5, 7, 1, 3, 6, 2]$ 进行归并排序，写出第一次归并后的结果。

习题 2

归并排序的时间复杂度和空间复杂度分别是多少？

上一章节堆排序介绍堆排序的基本思想、算法流程、复杂度分析及典型习题。

下一章节基数排序介绍基数排序的基本思想、算法流程、复杂度分析及典型习题。