归并排序代码出现Time Limit Exceeded错误，求优化方案

你的归并排序逻辑是正确的，但超时问题主要来自不必要的内存开销和可优化的细节，下面是几个关键优化点：

1. 避免重复创建大临时数组 #

当前merge函数每次都会创建和原数组等长的临时数组，这会导致频繁的内存分配与垃圾回收，极大拖慢性能。推荐的解决办法是：提前分配一次与原数组等长的临时数组，在所有合并操作中复用它，彻底减少重复分配的开销。

复用临时数组的示例修改：

void merge(int arr[], int temp[], int l, int m, int r) {
    int i = l;
    int j = m + 1;
    int k = l;

    while (i <= m && j <= r) {
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }

    // 复制剩余元素
    while (i <= m) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];

    // 用System.arraycopy替代手动循环，利用JVM底层优化
    System.arraycopy(temp, l, arr, l, r - l + 1);
}

void mergeSort(int arr[], int l, int r) {
    int[] temp = new int[arr.length]; // 仅初始化一次临时数组
    mergeSortHelper(arr, temp, l, r);
}

void mergeSortHelper(int arr[], int temp[], int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    mergeSortHelper(arr, temp, l, mid);
    mergeSortHelper(arr, temp, mid + 1, r);
    
    // 仅当两个子数组无序时才合并
    if (arr[mid] > arr[mid + 1]) {
        merge(arr, temp, l, mid, r);
    }
}

2. 修复mid计算的溢出问题 #

原代码中mid = (l + r) / 2，当l和r都是较大的整数时，l + r会超出int的取值范围导致溢出，改成mid = l + (r - l) / 2可以完全避免这个问题，同时计算结果和原逻辑一致。

3. 小数据量切换为插入排序 #

归并排序的递归和合并操作在处理极小的子数组时，常数时间开销比插入排序高。可以设置一个阈值（比如10~15），当子数组长度小于阈值时，直接使用插入排序替代归并：

void insertionSort(int arr[], int l, int r) {
    for (int i = l + 1; i <= r; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= l && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void mergeSortHelper(int arr[], int temp[], int l, int r) {
    // 子数组长度小于15时用插入排序
    if (r - l + 1 <= 15) {
        insertionSort(arr, l, r);
        return;
    }

    int mid = l + (r - l) / 2;
    mergeSortHelper(arr, temp, l, mid);
    mergeSortHelper(arr, temp, mid + 1, r);
    
    if (arr[mid] > arr[mid + 1]) {
        merge(arr, temp, l, mid, r);
    }
}

4. 跳过已有序的子数组合并 #

如果左子数组的最后一个元素小于等于右子数组的第一个元素，说明两个子数组本身已经是有序的，完全不需要执行合并操作，直接跳过这一步可以节省大量合并时间。

5. 优化数组复制操作 #

原代码中用for循环逐个复制元素，换成System.arraycopy方法可以利用JVM的底层优化，比手动循环的执行效率更高。

内容的提问来源于stack exchange，提问作者Mayur Panchal