基于递归层级结合插入排序的归并排序改进方案有效性验证

我们通过引入插入排序并利用**层级（level）**逻辑改进归并排序算法，规则是：在归并排序的两次递归调用前将层级参数加1，追踪递归树的层级索引，初始调用时层级设为1（递归树第一层索引为1）。

传统归并排序+插入排序改进方案 #

传统方案采用子数组长度阈值判断：当子数组长度≤阈值时，改用插入排序实现，代码如下：

static final int THRESHOLD = 10;
static void mergeSort(int f[],int lb, int ub){
    if (ub - lb <= THRESHOLD)
        insertionSort(f, lb, ub);
    else
    {
        int mid = (lb+ub)/2;
        mergeSort(f,lb,mid);
        mergeSort(f,mid,ub);
        merge(f,lb,mid,ub);
    }
}

基于层级逻辑的改进归并排序实现 #

我实现的方案通过递归树层级控制切换插入排序的时机，代码如下：

public static void merge_sort_improved(int [] A, int p, int r, int level, int max_level)
{
    int q = (int) Math.floor((p + r) / 2);       
    if (p < r)
    {
        if (level >= max_level)
            insertion_sort_2(A, p, r);      
        else
        {
            level++;
            merge_sort_improved(A, p, q, level, max_level);
            merge_sort_improved(A, q + 1, r, level, max_level);
        }
        merge(A, p, q, r);
        level--;
    }
}

测试结果 #

测试显示该方案整体比原生归并排序高效，部分场景下优于传统阈值改进方案，部分场景稍慢。具体测试数据如下：

Elapsed time in nanoseconds for original merge sort: 9551833
Elapsed time in nanoseconds for improved merge sort with max_level=13: 8766042
Max level: 1, Elapsed time in nanoseconds: 868102916
Max level: 2, Elapsed time in nanoseconds: 127934125
Max level: 3, Elapsed time in nanoseconds: 100636084
Max level: 4, Elapsed time in nanoseconds: 53176500
Max level: 5, Elapsed time in nanoseconds: 40008875
Max level: 6, Elapsed time in nanoseconds: 30925333
Max level: 7, Elapsed time in nanoseconds: 18650458
Max level: 8, Elapsed time in nanoseconds: 18098958
Max level: 9, Elapsed time in nanoseconds: 7862125
Max level: 10, Elapsed time in nanoseconds: 6666667
Max level: 11, Elapsed time in nanoseconds: 3863416
Max level: 12, Elapsed time in nanoseconds: 3646500
Max level: 13, Elapsed time in nanoseconds: 2776000
Max level: 14, Elapsed time in nanoseconds: 3010667
Max level: 15, Elapsed time in nanoseconds: 3280834
Max level: 16, Elapsed time in nanoseconds: 4677084
Max level: 17, Elapsed time in nanoseconds: 5324667
Best max level: 13, Min elapsed time in nanoseconds: 2776000

正确性验证与工作逻辑解析 #

工作逻辑 #

1. 层级追踪：初始调用时level=1，每进入下一层递归前执行level++，递归返回后执行level--，确保层级与递归树的深度严格对应。
2. 排序切换：当当前层级level >= max_level时，停止递归拆分，直接用插入排序处理当前子数组；否则继续递归拆分左右子数组，最后执行合并操作。
3. 合并保障：无论当前子数组是用插入排序完成排序，还是递归拆分后合并完成排序，最终都会执行merge操作，保证父级子数组的有序性。

正确性验证 #

• 递归终止逻辑：当p >= r时，子数组长度为1，天然有序；当level >= max_level时，插入排序能保证子数组有序，两种终止场景都能输出有序子数组。
• 合并逻辑合规：左右子数组均有序后，merge操作符合归并排序的核心规则，能将两个有序子数组合并为一个有序数组，最终保证整个数组完全有序。
• 性能变化符合预期：max_level过小时，插入排序处理的子数组过大，性能暴跌；随着max_level增大，插入排序处理的子数组逐渐变小，性能持续提升；当max_level过大时，算法几乎退化为原生归并排序，性能略有回落，这一变化趋势完全符合算法逻辑，侧面验证了正确性。

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