归并排序

定义与基本思想

归并排序（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]

时间复杂度分析

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

练习题

练习 1

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

参考答案

解题思路：分组后两两归并。

详细步骤：

1. 初始分组：[8,4],[5,7],[1,3],[6,2]
2. 第一次归并：[4,8],[5,7],[1,3],[2,6]

答案：如上，第一次归并后每组有序。

练习 2

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

参考答案

解题思路：考查复杂度和空间。

详细步骤：

1. 时间复杂度 $O(n\log n)$
2. 空间复杂度 $O(n)$

答案：时间 $O(n\log n)$，空间 $O(n)$。