为什么Java中的Merge Sort在同一个Array上变得更快

Question

我已经在Java中实现了合并排序.该类的实例名为ms.rArray是一个随机整数数组.为了测试,我使用以下代码运行它:

for (int i=0; i<10; i++) {
        System.out.println("Starting Merge Sort");
        testArray = rArray; // Create duplicate for testing
        long startM = System.currentTimeMillis();
        ms.sort(testArray);
        long stopM = System.currentTimeMillis();
        long durationM = stopM-startM;
        System.out.println("Size: " + size + "; Duration: " + durationM + "ms");
        System.out.println("++++++++++++++++++++++++++++++++++++++++++");
    }

输出:

Starting Merge Sort
Size: 1000000; Duration: 5853ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4527ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4082ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3000ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2930ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2904ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3403ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3570ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2930ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3133ms

每次运行都是相同的模式.为什么总是加速？我想它与编译器有关,因为Arrays.sort显示相同的行为.我不明白的是,如果我第一次运行Arrays.sort然后执行合并排序,为什么后者仍然比我自己运行合并排序的实现更快？

更新

System.arraycopy(rArray, 0, testArray, 0, rArray.length);按照Makoto的建议使用后(谢谢!),输出越来越好.但至于Merge排序则保持不变.我的合并排序实现不保存排序结果.那么加速JIT热身的原因是什么？

新产出:

Starting Default Sort
Size: 1000000; Duration: 1799ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 1816ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 945ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 944ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 944ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 943ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 957ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 963ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 964ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 952ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 5913ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3171ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3093ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4816ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3685ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3094ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3488ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3660ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3094ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3604ms

Answer 1

testArray = rArray.这不会创建重复.它只是创建了对rArray的新引用.所以,你正在排序已排序的数组.