排序(4)-归并排序专题——归并排序的分治美学

📌 引言

如果说快速排序是一位大开大合的“开拓者”，那归并排序（Merge Sort）就是一位步步为营的“哲学家”。它完美践行了计算机科学中最核心的分治思想（Divide and Conquer）。同时，它因为极其优秀的稳定性，成为了许多语言（包括 Java）实现工业级排序算法的绝对基石。

1. 归并排序（Merge Sort）

💡 核心思想

归并排序的核心可以用八个字概括：先分后治，合二为一。

• 分（Divide）：找到数组的中点，将其一分为二。递归地对左半部分和右半部分继续切分，直到子数组的长度为 1（长度为 1 的数组天然有序）。

• 治/合（Merge）：将两个已经有序的子数组合并成一个更大的、完全有序的数组。在这个过程中需要一个辅助数组来暂存数据。

💻 Java 代码实现（高性能标准版）

public class MergeSort { public static void sort(int[] arr) { if (arr == null || arr.length < 2) return; // 关键优化：预先分配好辅助空间，避免在递归方法中频繁 new 数组导致内存碎片 int[] aux = new int[arr.length]; sort(arr, 0, arr.length - 1, aux); } private static void sort(int[] arr, int left, int right, int[] aux) { if (left >= right) return; // 递归基：子数组长度为 1 int mid = left + (right - left) / 2; // 防溢出的中点写法 sort(arr, left, mid, aux); // 递归使左半部分有序 sort(arr, mid + 1, right, aux); // 递归使右半部分有序 // 优化：如果左边的最大值已经小于等于右边的最小值，说明已经整体有序，无需 merge if (arr[mid] > arr[mid + 1]) { merge(arr, left, mid, right, aux); // 核心合并操作 } } private static void merge(int[] arr, int left, int mid, int right, int[] aux) { // 1. 将当前区间的元素复制到辅助数组 for (int k = left; k <= right; k++) { aux[k] = arr[k]; } // 2. 双指针合并 int i = left; // 左半部分指针 int j = mid + 1; // 右半部分指针 for (int k = left; k <= right; k++) { if (i > mid) { arr[k] = aux[j++]; // 左半边已用尽，直接取右半边 } else if (j > right) { arr[k] = aux[i++]; // 右半边已用尽，直接取左半边 } else if (aux[i] <= aux[j]) { arr[k] = aux[i++]; // 左边小或相等，取左边（这里的 <= 保证了算法的稳定性） } else { arr[k] = aux[j++]; // 右边小，取右边 } } } }

📊 性能分析

• 时间复杂度：无论数组初始状态如何，归并排序的递归树层数都是 \log n，每层合并的开销都是 O(n)。因此，它的最好、最坏、平均时间复杂度全都是严格的O(n \log n)。

• 空间复杂度：O(n)。由于在合并阶段需要和原数组等长的辅助数组来暂存元素，这是它相比于快排和堆排序最大的劣势（空间换时间）。

• 稳定性：稳定。只要在merge逻辑中，当左右指针元素相等时优先采用左侧元素（aux[i] <= aux[j]），就能完美保持相同元素的相对顺序。