归并排序

算法定义

归并排序（Merge Sort）是一种基于 "分治法"（Divide and Conquer）的排序算法，由约翰・冯・诺依曼在 1945 年提出。它将一个大数组分解为两个较小的子数组，递归地排序每个子数组，然后将排序好的子数组合并成一个有序的数组。

算法思路

归并排序的核心思想是 "先分后合"，具体步骤如下：

分解（Divide）：将原始数组递归地分成两个规模大致相等的子数组，直到每个子数组只包含一个元素（单个元素自然是有序的）。
合并（Merge）：将两个已排序的子数组合并成一个更大的有序数组。这一步是归并排序的核心操作。
递归终止：当子数组的长度为 1 时，停止递归，开始向上合并。

合并操作的关键是创建一个临时数组，比较两个子数组的元素，按顺序将较小的元素放入临时数组，最后将临时数组的内容复制回原数组。

算法复杂度

最好时间复杂度：O (n log n) - 无论输入数据是否有序，归并排序的时间复杂度都保持稳定
最坏时间复杂度：O (n log n) - 即使数组完全逆序，排序效率也不受影响
平均时间复杂度：O(n log n)
空间复杂度：O (n) - 需要额外的临时数组用于合并操作

优点与缺点

优点：
- 时间复杂度稳定，始终为 O (n log n)，不受输入数据分布影响
- 稳定的排序算法（相等元素的相对位置保持不变）
- 适合处理大规模数据，尤其是外部排序
- 对链表排序效率高，不需要大量随机访问
缺点：
- 需要额外的 O (n) 存储空间
- 对于小规模数据，效率不如插入排序等简单算法
- 合并操作涉及较多的数据复制，可能影响性能

应用场景

需要稳定排序的场景（如电商订单按价格和时间双重排序）
外部排序（数据量超过内存，需要磁盘存储时）
链表排序（可以实现 O (1) 的额外空间复杂度）
对排序稳定性要求高，且可以接受额外空间开销的场景

各版本优化说明

基本版（递归实现）：
- 标准的归并排序实现，采用递归分治策略
- 清晰展示了归并排序 "分 - 合" 的核心思想
混合插入排序优化：
- 当子数组长度小于阈值（通常 15-20）时，使用插入排序
- 增加了一个判断：只有当两个子数组需要合并时才执行合并操作
- 利用插入排序在小规模数据上的优势，减少递归和合并开销
非递归（迭代）实现：
- 避免了递归调用的栈开销
- 从子数组长度 1 开始，逐步合并更大的子数组
- 对于某些编程语言和环境，迭代版本可能更高效
优化复制操作：
- 通过两个数组交替作为源和目标，减少数据复制次数
- 使用System.arraycopy替代手动循环复制，提高效率
- 当子数组已经有序时，直接复制而不进行合并操作

归并排序是一种高效且稳定的排序算法，虽然需要额外的空间，但在对稳定性要求高或处理大规模数据时是很好的选择。Java 的Arrays.sort()方法在处理对象数组时就采用了归并排序的变体（TimSort）。

代码

import java.util.Arrays;

public class MergeSort {
    
    // 1. 基本版归并排序（递归实现）
    public static void mergeSortBasic(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length]; // 临时数组
        mergeSortBasic(arr, 0, arr.length - 1, temp);
    }
    
    private static void mergeSortBasic(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2; // 避免溢出
            
            // 递归排序左半部分
            mergeSortBasic(arr, left, mid, temp);
            // 递归排序右半部分
            mergeSortBasic(arr, mid + 1, right, temp);
            
            // 合并两个有序子数组
            mergeBasic(arr, left, mid, right, temp);
        }
    }
    
    private static void mergeBasic(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;     // 左子数组起始索引
        int j = mid + 1;  // 右子数组起始索引
        int t = 0;        // 临时数组起始索引
        
        // 比较两个子数组元素，放入临时数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        
        // 处理左子数组剩余元素
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        
        // 处理右子数组剩余元素
        while (j <= right) {
            temp[t++] = arr[j++];
        }
        
        // 将临时数组元素复制回原数组
        t = 0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
    
    // 2. 优化版1：小规模数据使用插入排序
    public static void mergeSortHybrid(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSortHybrid(arr, 0, arr.length - 1, temp);
    }
    
    private static void mergeSortHybrid(int[] arr, int left, int right, int[] temp) {
        // 当子数组长度小于阈值时，使用插入排序
        if (right - left + 1 <= 15) {
            insertionSort(arr, left, right);
            return;
        }
        
        int mid = left + (right - left) / 2;
        mergeSortHybrid(arr, left, mid, temp);
        mergeSortHybrid(arr, mid + 1, right, temp);
        
        // 只有当左子数组的最后一个元素大于右子数组的第一个元素时才需要合并
        if (arr[mid] > arr[mid + 1]) {
            mergeBasic(arr, left, mid, right, temp);
        }
    }
    
    // 插入排序（用于小规模数据）
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    // 3. 优化版2：非递归（迭代）实现
    public static void mergeSortIterative(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        int[] temp = new int[n];
        
        // 子数组长度从1开始，每次翻倍
        for (int size = 1; size < n; size *= 2) {
            // 遍历所有子数组
            for (int left = 0; left < n - size; left += 2 * size) {
                int mid = left + size - 1;
                int right = Math.min(left + 2 * size - 1, n - 1);
                mergeBasic(arr, left, mid, right, temp);
            }
        }
    }
    
    // 4. 优化版3：减少复制操作的归并
    public static void mergeSortOptimizedCopy(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 创建原数组的副本，避免在合并时频繁复制
        int[] copy = Arrays.copyOf(arr, arr.length);
        mergeSortOptimizedCopy(arr, copy, 0, arr.length - 1);
    }
    
    private static void mergeSortOptimizedCopy(int[] dest, int[] src, int left, int right) {
        if (left >= right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        
        // 交换源数组和目标数组，减少复制操作
        mergeSortOptimizedCopy(src, dest, left, mid);
        mergeSortOptimizedCopy(src, dest, mid + 1, right);
        
        // 合并操作直接写入目标数组
        if (src[mid] <= src[mid + 1]) {
            System.arraycopy(src, left, dest, left, right - left + 1);
            return;
        }
        
        int i = left;
        int j = mid + 1;
        int k = left;
        
        while (i <= mid && j <= right) {
            if (src[i] <= src[j]) {
                dest[k++] = src[i++];
            } else {
                dest[k++] = src[j++];
            }
        }
        
        while (i <= mid) {
            dest[k++] = src[i++];
        }
        
        while (j <= right) {
            dest[k++] = src[j++];
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90, 5};
        int[] arr1 = Arrays.copyOf(arr, arr.length);
        int[] arr2 = Arrays.copyOf(arr, arr.length);
        int[] arr3 = Arrays.copyOf(arr, arr.length);
        int[] arr4 = Arrays.copyOf(arr, arr.length);
        
        mergeSortBasic(arr1);
        System.out.println("基本版（递归）: " + Arrays.toString(arr1));
        
        mergeSortHybrid(arr2);
        System.out.println("混合插入排序: " + Arrays.toString(arr2));
        
        mergeSortIterative(arr3);
        System.out.println("非递归实现: " + Arrays.toString(arr3));
        
        mergeSortOptimizedCopy(arr4);
        System.out.println("优化复制操作: " + Arrays.toString(arr4));
    }
}