如何在数组中查找已排序子数组以优化mergeSort归并排序算法

优化核心思路 #

原版归并排序会无条件递归拆分、合并所有子数组，忽略了数组中原本就存在的连续有序区间。我们可以增加有序性判断跳过不必要的合并操作：

• 左右子数组各自完成排序后，先判断左子数组的最大值（即左子数组最后一个元素）是否小于等于右子数组的最小值（即右子数组第一个元素），如果满足条件说明两个子数组拼接后已经是整体有序状态，不需要再执行双指针合并逻辑，直接复制数组即可。
• 额外可选优化：当子数组长度小于15（可根据场景调整阈值）时直接用插入排序排序，小数据量下插入排序性能优于归并排序。

优化后代码实现 #

public static void mergeSort(int[] array)
{
    if(array == null || array.length <= 1)
    {
        return;
    }

    int mid = array.length / 2;

    // left
    int[] left = new int[mid];
    for(int i = 0; i < mid; i++)
    {
        left[i] = array[i];
    }
     
    //right
    int[] right = new int[array.length - mid];
    for(int i = mid; i < array.length; i++)
    {
        right[i - mid] = array[i];
    }
    //recursively calls
    mergeSort(left);
    mergeSort(right);

    // 新增优化点：左右子数组已经天然有序，直接拼接即可
    if (left[left.length - 1] <= right[0]) {
        System.arraycopy(left, 0, array, 0, left.length);
        System.arraycopy(right, 0, array, left.length, right.length);
        return;
    }

    int i = 0;
    int j = 0;
    int k = 0;

    //  left and right merged
    while(i < left.length && j < right.length)
    {
        if(left[i] < right[j])
        {
            array[k] = left[i];
            i++;
        }
        else
        {
            array[k] = right[j];
            j++;
        }
        k++;
    }
    // left overs
    while(i < left.length)
    {
        array[k] = left[i];
        i++;
        k++;
    }
    while(j < right.length)
    {
        array[k] = right[j];
        j++;
        k++;
    }
}

优化效果说明 #

• 对于完全有序的数组，时间复杂度直接降为O(n)，不需要执行任何双指针合并操作
• 对于有序度较高的数组，可大幅减少合并操作的次数，性能提升幅度可达数倍
• 最坏情况（完全逆序数组）下和原版归并排序性能一致，不会产生额外性能损耗

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