使用JMH基准测试冒泡排序与归并排序：结果异常求排查

核心问题：复用已排序数组导致测试失真 #

你的基准测试代码存在致命缺陷：每次迭代都使用同一个数组实例。第一次排序后，数组已经完全有序，后续所有迭代都是对有序数组进行排序：

• 冒泡排序在数组有序时，内层循环的arr[j]<arr[j-1]判断始终为false，不会执行任何交换操作，实际时间复杂度降为O(n)
• 归并排序不管数组是否有序，都会执行完整的分治递归和合并流程，时间复杂度保持O(nlogn)，还要承担递归调用、临时数组创建的额外开销

这直接导致测试结果完全不符合算法的理论复杂度特性。

其他影响测试结果的因素 #

• 测试数据规模过小：当前测试数组仅约80个元素，归并排序的O(nlogn)复杂度优势在小数据量下无法抵消其常数开销（递归调用、临时数组分配），而冒泡排序的常数项更低，小数据量下本身就可能表现接近甚至更好。
• 未防止JVM优化：虽然排序操作修改了数组，但最好显式使用JMH的Blackhole来确保操作不被JVM优化消除，避免测试结果失真。
• 归并排序的临时数组开销：你的归并实现每次merge都会创建两个新的临时数组L和R，频繁的内存分配在小数据量下会带来明显的性能损耗。

算法实现正确性 #

两种排序的实现本身都是正确的：

• 冒泡排序从后往前遍历，每轮将最小元素移动到前面，逻辑无误
• 归并排序的分治和合并逻辑符合标准实现，没有逻辑错误

修复建议 #

1. 每次迭代创建新数组：避免复用已排序的数组，确保每次迭代都拿到未排序的新数组，示例：

   @Benchmark
   public void testMergeSort(Blackhole bh) {
       // 每次benchmark都生成新的未排序数组
       int[] arr = {3,2,2,2,1,3,2,3,2,3,0,1,22,9,12,44,55,1000,99,33,333,4,33339,32,3,444,332345,32939,39493,3,2,2,2,1,3,2,3,2,3,0,1,22,9,12,44,55,1000,99,33,333,4,33339,32,3,444,332345,32939,39493,3,2,2,2,1,3,2,3,2,3,0,1,22,9,12,44,55,1000,99,33,333,4,33339,32,3,444,332345,32939,39493};
       mergeSort(arr, 0, arr.length-1);
       bh.consume(arr);
   }
   

2. 扩大测试数据规模：测试至少1000个以上的随机元素，才能体现归并排序的复杂度优势。
3. 优化归并排序的临时数组：预先分配一个全局临时数组，在merge时复用，避免频繁创建新数组，减少内存开销。
4. 使用JMH的Blackhole：显式消费排序后的数组，防止JVM将排序操作判定为无用代码而优化。

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