归并排序

归并排序（Merge Sort）是基于分治法的排序算法，由 John von Neumann 在 1945 年提出。"归并"是指将两个或多个已经有序的序列合并为一个有序序列的过程。

核心思想

1. 分解（Divide）：将长度为 n 的序列分成两个长度为 n/2 的子序列
2. 解决（Conquer）：递归地对两个子序列进行归并排序
3. 合并（Merge）：将两个已排序的子序列合并为一个有序序列

归并排序的递归树是一棵倒立的完全二叉树，每层归并的时间复杂度为 $O(n)$，共 $\log_2 n$ 层，总时间复杂度为 $O(n\log_2 n)$。

关键特性

• 归并排序是稳定的排序算法
• 时间复杂度始终为 $O(n\log_2 n)$，与初始序列无关（最好、最坏、平均都一样）
• 需要额外的 $O(n)$ 空间用于合并操作，是内部排序中空间消耗最大的
• 适合对链表进行排序（不需要额外空间）
• 是外部排序的基础算法

二路归并排序过程

1. 分解：将长度为 n 的序列从中间分成两半，得到两个子序列
2. 递归排序：对左子序列和右子序列分别递归执行归并排序
3. 合并：将两个已排序的子序列合并为一个有序序列

合并（Merge）过程

设两个有序子序列为 L[i..m] 和 L[m+1..r]，合并步骤：

1. 设置三个指针：i 指向第一个子序列开头，j 指向第二个子序列开头，k 指向辅助数组开头
2. 比较 L[i] 和 L[j]，将较小的元素放入辅助数组 temp[k]，相应指针后移
3. 重复步骤 2，直到某个子序列的所有元素都已放入辅助数组
4. 将另一个子序列的剩余元素全部复制到辅助数组末尾
5. 将辅助数组中的有序结果复制回原数组

归并趟数

n 个元素进行二路归并排序，归并趟数为 $\lceil\log_2 n\rceil$。

// 合并两个有序子序列 A[low..mid] 和 A[mid+1..high]
void Merge(int A[], int low, int mid, int high) {
    // 将 A 中元素复制到辅助数组 temp
    for (int k = low; k <= high; k++)
        temp[k] = A[k];

    int i = low, j = mid + 1, k = low;
    // 比较两个子序列的元素，按顺序放入原数组
    while (i <= mid && j <= high) {
        if (temp[i] <= temp[j])  // 注意：<= 保证稳定性
            A[k++] = temp[i++];
        else
            A[k++] = temp[j++];
    }
    // 处理剩余元素
    while (i <= mid) A[k++] = temp[i++];
    while (j <= high) A[k++] = temp[j++];
}

// 归并排序（递归实现）
void MergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;  // 从中间划分
        MergeSort(A, low, mid);            // 对左半部分归并排序
        MergeSort(A, mid + 1, high);       // 对右半部分归并排序
        Merge(A, low, mid, high);          // 合并两个有序子序列
    }
}

// 初始化调用
void Sort(int A[], int n) {
    temp = (int *)malloc(n * sizeof(int));
    MergeSort(A, 0, n - 1);
    free(temp);
}