跳转至
纸质书已发行，详情请见这里

# 11.6 归并排序

归并排序（merge sort）是一种基于分治策略的排序算法，包含图 11-10 所示的“划分”和“合并”阶段。

1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

图 11-10 归并排序的划分与合并阶段

## 11.6.1 算法流程

如图 11-11 所示，“划分阶段”从顶至底递归地将数组从中点切分为两个子数组。

1. 计算数组中点 `mid` ，递归划分左子数组（区间 `[left, mid]` ）和右子数组（区间 `[mid + 1, right]` ）。
2. 递归执行步骤 `1.` ，直至子数组区间长度为 1 时终止。

“合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的。

<1><2><3><4><5><6><7><8><9><10>

图 11-11 归并排序步骤

观察发现，归并排序与二叉树后序遍历的递归顺序是一致的。

- 后序遍历：先递归左子树，再递归右子树，最后处理根节点。
- 归并排序：先递归左子数组，再递归右子数组，最后处理合并。

归并排序的实现如以下代码所示。请注意，`nums` 的待合并区间为 `[left, right]` ，而 `tmp` 的对应区间为 `[0, right - left]` 。

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
merge_sort.py

    def merge(nums: list[int], left: int, mid: int, right: int):
        """合并左子数组和右子数组"""
        # 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        # 创建一个临时数组 tmp ，用于存放合并后的结果
        tmp = [0] * (right - left + 1)
        # 初始化左子数组和右子数组的起始索引
        i, j, k = left, mid + 1, 0
        # 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while i <= mid and j <= right:
            if nums[i] <= nums[j]:
                tmp[k] = nums[i]
                i += 1
            else:
                tmp[k] = nums[j]
                j += 1
            k += 1
        # 将左子数组和右子数组的剩余元素复制到临时数组中
        while i <= mid:
            tmp[k] = nums[i]
            i += 1
            k += 1
        while j <= right:
            tmp[k] = nums[j]
            j += 1
            k += 1
        # 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for k in range(0, len(tmp)):
            nums[left + k] = tmp[k]

    def merge_sort(nums: list[int], left: int, right: int):
        """归并排序"""
        # 终止条件
        if left >= right:
            return  # 当子数组长度为 1 时终止递归
        # 划分阶段
        mid = (left + right) // 2 # 计算中点
        merge_sort(nums, left, mid)  # 递归左子数组
        merge_sort(nums, mid + 1, right)  # 递归右子数组
        # 合并阶段
        merge(nums, left, mid, right)

merge_sort.cpp

    /* 合并左子数组和右子数组 */
    void merge(vector<int> &nums, int left, int mid, int right) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        vector<int> tmp(right - left + 1);
        // 初始化左子数组和右子数组的起始索引
        int i = left, j = mid + 1, k = 0;
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for (k = 0; k < tmp.size(); k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* 归并排序 */
    void mergeSort(vector<int> &nums, int left, int right) {
        // 终止条件
        if (left >= right)
            return; // 当子数组长度为 1 时终止递归
        // 划分阶段
        int mid = left + (right - left) / 2;    // 计算中点
        mergeSort(nums, left, mid);      // 递归左子数组
        mergeSort(nums, mid + 1, right); // 递归右子数组
        // 合并阶段
        merge(nums, left, mid, right);
    }

merge_sort.java

    /* 合并左子数组和右子数组 */
    void merge(int[] nums, int left, int mid, int right) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        int[] tmp = new int[right - left + 1];
        // 初始化左子数组和右子数组的起始索引
        int i = left, j = mid + 1, k = 0;
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* 归并排序 */
    void mergeSort(int[] nums, int left, int right) {
        // 终止条件
        if (left >= right)
            return; // 当子数组长度为 1 时终止递归
        // 划分阶段
        int mid = left + (right - left) / 2; // 计算中点
        mergeSort(nums, left, mid); // 递归左子数组
        mergeSort(nums, mid + 1, right); // 递归右子数组
        // 合并阶段
        merge(nums, left, mid, right);
    }

merge_sort.cs

    /* 合并左子数组和右子数组 */
    void Merge(int[] nums, int left, int mid, int right) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        int[] tmp = new int[right - left + 1];
        // 初始化左子数组和右子数组的起始索引
        int i = left, j = mid + 1, k = 0;
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for (k = 0; k < tmp.Length; ++k) {
            nums[left + k] = tmp[k];
        }
    }

    /* 归并排序 */
    void MergeSort(int[] nums, int left, int right) {
        // 终止条件
        if (left >= right) return;       // 当子数组长度为 1 时终止递归
        // 划分阶段
        int mid = left + (right - left) / 2;    // 计算中点
        MergeSort(nums, left, mid);      // 递归左子数组
        MergeSort(nums, mid + 1, right); // 递归右子数组
        // 合并阶段
        Merge(nums, left, mid, right);
    }

merge_sort.go

    /* 合并左子数组和右子数组 */
    func merge(nums []int, left, mid, right int) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        tmp := make([]int, right-left+1)
        // 初始化左子数组和右子数组的起始索引
        i, j, k := left, mid+1, 0
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        for i <= mid && j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i]
                i++
            } else {
                tmp[k] = nums[j]
                j++
            }
            k++
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        for i <= mid {
            tmp[k] = nums[i]
            i++
            k++
        }
        for j <= right {
            tmp[k] = nums[j]
            j++
            k++
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for k := 0; k < len(tmp); k++ {
            nums[left+k] = tmp[k]
        }
    }

    /* 归并排序 */
    func mergeSort(nums []int, left, right int) {
        // 终止条件
        if left >= right {
            return
        }
        // 划分阶段
        mid := left + (right - left) / 2
        mergeSort(nums, left, mid)
        mergeSort(nums, mid+1, right)
        // 合并阶段
        merge(nums, left, mid, right)
    }

merge_sort.swift

    /* 合并左子数组和右子数组 */
    func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        var tmp = Array(repeating: 0, count: right - left + 1)
        // 初始化左子数组和右子数组的起始索引
        var i = left, j = mid + 1, k = 0
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while i <= mid, j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i]
                i += 1
            } else {
                tmp[k] = nums[j]
                j += 1
            }
            k += 1
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while i <= mid {
            tmp[k] = nums[i]
            i += 1
            k += 1
        }
        while j <= right {
            tmp[k] = nums[j]
            j += 1
            k += 1
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for k in tmp.indices {
            nums[left + k] = tmp[k]
        }
    }

    /* 归并排序 */
    func mergeSort(nums: inout [Int], left: Int, right: Int) {
        // 终止条件
        if left >= right { // 当子数组长度为 1 时终止递归
            return
        }
        // 划分阶段
        let mid = left + (right - left) / 2 // 计算中点
        mergeSort(nums: &nums, left: left, right: mid) // 递归左子数组
        mergeSort(nums: &nums, left: mid + 1, right: right) // 递归右子数组
        // 合并阶段
        merge(nums: &nums, left: left, mid: mid, right: right)
    }

merge_sort.js

    /* 合并左子数组和右子数组 */
    function merge(nums, left, mid, right) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        const tmp = new Array(right - left + 1);
        // 初始化左子数组和右子数组的起始索引
        let i = left,
            j = mid + 1,
            k = 0;
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* 归并排序 */
    function mergeSort(nums, left, right) {
        // 终止条件
        if (left >= right) return; // 当子数组长度为 1 时终止递归
        // 划分阶段
        let mid = Math.floor(left + (right - left) / 2); // 计算中点
        mergeSort(nums, left, mid); // 递归左子数组
        mergeSort(nums, mid + 1, right); // 递归右子数组
        // 合并阶段
        merge(nums, left, mid, right);
    }

merge_sort.ts

    /* 合并左子数组和右子数组 */
    function merge(nums: number[], left: number, mid: number, right: number): void {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        const tmp = new Array(right - left + 1);
        // 初始化左子数组和右子数组的起始索引
        let i = left,
            j = mid + 1,
            k = 0;
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* 归并排序 */
    function mergeSort(nums: number[], left: number, right: number): void {
        // 终止条件
        if (left >= right) return; // 当子数组长度为 1 时终止递归
        // 划分阶段
        let mid = Math.floor(left + (right - left) / 2); // 计算中点
        mergeSort(nums, left, mid); // 递归左子数组
        mergeSort(nums, mid + 1, right); // 递归右子数组
        // 合并阶段
        merge(nums, left, mid, right);
    }

merge_sort.dart

    /* 合并左子数组和右子数组 */
    void merge(List<int> nums, int left, int mid, int right) {
      // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
      // 创建一个临时数组 tmp ，用于存放合并后的结果
      List<int> tmp = List.filled(right - left + 1, 0);
      // 初始化左子数组和右子数组的起始索引
      int i = left, j = mid + 1, k = 0;
      // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
      while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
          tmp[k++] = nums[i++];
        else
          tmp[k++] = nums[j++];
      }
      // 将左子数组和右子数组的剩余元素复制到临时数组中
      while (i <= mid) {
        tmp[k++] = nums[i++];
      }
      while (j <= right) {
        tmp[k++] = nums[j++];
      }
      // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
      for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
      }
    }

    /* 归并排序 */
    void mergeSort(List<int> nums, int left, int right) {
      // 终止条件
      if (left >= right) return; // 当子数组长度为 1 时终止递归
      // 划分阶段
      int mid = left + (right - left) ~/ 2; // 计算中点
      mergeSort(nums, left, mid); // 递归左子数组
      mergeSort(nums, mid + 1, right); // 递归右子数组
      // 合并阶段
      merge(nums, left, mid, right);
    }

merge_sort.rs

    /* 合并左子数组和右子数组 */
    fn merge(nums: &mut [i32], left: usize, mid: usize, right: usize) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        let tmp_size = right - left + 1;
        let mut tmp = vec![0; tmp_size];
        // 初始化左子数组和右子数组的起始索引
        let (mut i, mut j, mut k) = (left, mid + 1, 0);
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while i <= mid && j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i];
                i += 1;
            } else {
                tmp[k] = nums[j];
                j += 1;
            }
            k += 1;
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while i <= mid {
            tmp[k] = nums[i];
            k += 1;
            i += 1;
        }
        while j <= right {
            tmp[k] = nums[j];
            k += 1;
            j += 1;
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for k in 0..tmp_size {
            nums[left + k] = tmp[k];
        }
    }

    /* 归并排序 */
    fn merge_sort(nums: &mut [i32], left: usize, right: usize) {
        // 终止条件
        if left >= right {
            return; // 当子数组长度为 1 时终止递归
        }

        // 划分阶段
        let mid = left + (right - left) / 2; // 计算中点
        merge_sort(nums, left, mid); // 递归左子数组
        merge_sort(nums, mid + 1, right); // 递归右子数组

        // 合并阶段
        merge(nums, left, mid, right);
    }

merge_sort.c

    /* 合并左子数组和右子数组 */
    void merge(int *nums, int left, int mid, int right) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        int tmpSize = right - left + 1;
        int *tmp = (int *)malloc(tmpSize * sizeof(int));
        // 初始化左子数组和右子数组的起始索引
        int i = left, j = mid + 1, k = 0;
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for (k = 0; k < tmpSize; ++k) {
            nums[left + k] = tmp[k];
        }
        // 释放内存
        free(tmp);
    }

    /* 归并排序 */
    void mergeSort(int *nums, int left, int right) {
        // 终止条件
        if (left >= right)
            return; // 当子数组长度为 1 时终止递归
        // 划分阶段
        int mid = left + (right - left) / 2;    // 计算中点
        mergeSort(nums, left, mid);      // 递归左子数组
        mergeSort(nums, mid + 1, right); // 递归右子数组
        // 合并阶段
        merge(nums, left, mid, right);
    }

merge_sort.kt

    /* 合并左子数组和右子数组 */
    fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
        // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        val tmp = IntArray(right - left + 1)
        // 初始化左子数组和右子数组的起始索引
        var i = left
        var j = mid + 1
        var k = 0
        // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++]
            else
                tmp[k++] = nums[j++]
        }
        // 将左子数组和右子数组的剩余元素复制到临时数组中
        while (i <= mid) {
            tmp[k++] = nums[i++]
        }
        while (j <= right) {
            tmp[k++] = nums[j++]
        }
        // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
        for (l in tmp.indices) {
            nums[left + l] = tmp[l]
        }
    }

    /* 归并排序 */
    fun mergeSort(nums: IntArray, left: Int, right: Int) {
        // 终止条件
        if (left >= right) return  // 当子数组长度为 1 时终止递归
        // 划分阶段
        val mid = left + (right - left) / 2 // 计算中点
        mergeSort(nums, left, mid) // 递归左子数组
        mergeSort(nums, mid + 1, right) // 递归右子数组
        // 合并阶段
        merge(nums, left, mid, right)
    }

merge_sort.rb

    ### 合并左子数组和右子数组 ###
    def merge(nums, left, mid, right)
      # 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
      # 创建一个临时数组 tmp，用于存放合并后的结果
      tmp = Array.new(right - left + 1, 0)
      # 初始化左子数组和右子数组的起始索引
      i, j, k = left, mid + 1, 0
      # 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
      while i <= mid && j <= right
        if nums[i] <= nums[j]
          tmp[k] = nums[i]
          i += 1
        else
          tmp[k] = nums[j]
          j += 1
        end
        k += 1
      end
      # 将左子数组和右子数组的剩余元素复制到临时数组中
      while i <= mid
        tmp[k] = nums[i]
        i += 1
        k += 1
      end
      while j <= right
        tmp[k] = nums[j]
        j += 1
        k += 1
      end
      # 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
      (0...tmp.length).each do |k|
        nums[left + k] = tmp[k]
      end
    end

    ### 归并排序 ###
    def merge_sort(nums, left, right)
      # 终止条件
      # 当子数组长度为 1 时终止递归
      return if left >= right
      # 划分阶段
      mid = left + (right - left) / 2 # 计算中点
      merge_sort(nums, left, mid) # 递归左子数组
      merge_sort(nums, mid + 1, right) # 递归右子数组
      # 合并阶段
      merge(nums, left, mid, right)
    end

可视化运行

全屏观看 >

## 11.6.2 算法特性

- 时间复杂度为 \(O(n \log n)\)、非自适应排序：划分产生高度为 \(\log n\) 的递归树，每层合并的总操作数量为 \(n\) ，因此总体时间复杂度为 \(O(n \log n)\) 。
- 空间复杂度为 \(O(n)\)、非原地排序：递归深度为 \(\log n\) ，使用 \(O(\log n)\) 大小的栈帧空间。合并操作需要借助辅助数组实现，使用 \(O(n)\) 大小的额外空间。
- 稳定排序：在合并过程中，相等元素的次序保持不变。

## 11.6.3 链表排序

对于链表，归并排序相较于其他排序算法具有显著优势，可以将链表排序任务的空间复杂度优化至 \(O(1)\) 。

- 划分阶段：可以使用“迭代”替代“递归”来实现链表划分工作，从而省去递归使用的栈帧空间。
- 合并阶段：在链表中，节点增删操作仅需改变引用（指针）即可实现，因此合并阶段（将两个短有序链表合并为一个长有序链表）无须创建额外链表。

具体实现细节比较复杂，有兴趣的读者可以查阅相关资料进行学习。

##### 欢迎在评论区留下你的见解、问题或建议