---

版权声明

• 本文原创作者：谷哥的小弟
• 作者博客地址：http://blog.csdn.net/lfdfhl

---

基本原理

归并排序基于分治思想，递归地将数组拆分为两个子数组，分别排序后合并。时间复杂度为 O(n log n)，空间复杂度 O(n)（需额外存储合并后的数组），是稳定排序，适用于大数据量且对稳定性有要求的场景（如外部排序）。

代码实现

import java.util.Arrays;public class MergeSort {public static void mergeSort(int[] arr, int left, int right) {if (left < right) { // 递归终止条件：子数组长度大于1int mid = left + (right - left) / 2;mergeSort(arr, left, mid);    // 递归排序左半部分mergeSort(arr, mid + 1, right); // 递归排序右半部分merge(arr, left, mid, right);  // 合并两个有序子数组}}private static void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left + 1]; // 临时存储合并结果int i = left, j = mid + 1, k = 0;// 合并两个子数组while (i <= mid && j <= right) {temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++]; // 稳定排序的关键}// 处理剩余元素while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];// 将合并结果复制回原数组System.arraycopy(temp, 0, arr, left, temp.length);}public static void main(String[] args) {int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};mergeSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));// 输出：Sorted array: [1, 2, 3, 4, 5, 6, 7, 8]}
}