归并插入混合排序实现性能提升不明显，是否存在代码错误？

实现存在的错误 #

• 插入排序的边界逻辑错误：你当前insertionSort实现中，while循环的终止条件写的是j >= 0，但你处理的是[start, end)区间的子数组，正确的边界应该是j >= start。这个错误会导致插入排序时修改子数组外的元素，既可能破坏其他位置的排序结果，也让插入排序的实际优化效果完全无法体现。
• 比较次数统计逻辑错误：你将comparisons++写在了while循环内部，只有当arr[j] > key时才会计数，但实际每次arr[j] > key的判断都属于一次比较，包括判断为假、跳出循环的那次，导致统计的比较次数远低于实际值，你观察到的“仅减少2-3次”的结论本身就不成立。
• 阈值设置过小：你当前设置的阈值是r - l < 3，也就是仅对长度≤2的子数组切换插入排序。这么小的长度下，归并排序的开销本身就极低，完全体现不出插入排序的优势。通常混合排序的阈值建议设置为10~30之间，比如15或20，才能观测到明显的性能收益。

性能测试的问题 #

你当前的测试样本太小，仅使用了长度几十的数组，两种排序的差异会被系统调度、缓存等噪声完全覆盖。想要观测到性能差异，建议：

• 测试长度≥10万的随机数组
• 不要只统计比较次数，要统计实际运行耗时：插入排序的优势并非减少比较次数，而是原地排序、缓存友好，避免了归并排序中小子数组的临时内存申请、数据拷贝开销，这些开销在比较次数里完全体现不出来。

修复建议 #

把insertionSort里的while条件改成j >= start && arr[j] > key，同时把comparisons++移到while条件判断之前，再把阈值调整为15左右，用大数组测试就能看到明显的性能提升。

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