我正在对长度为 10,000 到 75,000 的 int 数组进行合并排序。我的排序时间变得很奇怪。为什么会这样？

Question

我正在为我的算法类做作业，我必须证明内部合并排序的时间复杂度为O(n log n)。为此，我创建了长度从 10,000 个元素到 75,000 个元素的数组。然后我用低于 10,000 的随机数加载数组，并将数组长度输出到控制台，并显示排序所需的时间。

奇怪的结果是，有些需要大约 15 毫秒的时间，而另一些则需要 0 毫秒，即使数组长了数万个整数。知道为什么会这样吗？我可以上传我的输出的屏幕截图，但需要有人批准它，因为我没有足够的“声誉”。我已经检查了数组。调用该方法后，它们似乎确实已排序mergeSort()。

public static void main(String[] args){
    int[] dataLength = { 10_000, 15_000, 20_000, 25_000, 30_000,
                         35_000, 40_000, 45_000, 50_000, 55_000,
                         60_000, 65_000, 70_000, 75_000 };
    // internal merge sort
    for (int i = 0; i < dataLength.length; i++) {
        int[] input = new int[dataLength[i]];
        for (int j = 0; j < input.length; j++) {
            input[j] = random.nextInt(10000);
        }

        long startTime = System.currentTimeMillis();
        mergeSort(input, 0, input.length);
        long endTime = System.currentTimeMillis();

        System.out.println("Length of array is: " + input.length + ". The sorted array: " +
                           Arrays.toString(input));
        System.out.println("Internal sort with " + dataLength[i] + " items took: " +
                           (endTime - startTime) + " milliseconds");
    }
}

public static void mergeSort(int[] input, int start, int end) {
    if (end - start < 2) {
        return;
    }

    int mid = (start + end) / 2;
    mergeSort(input, start, mid);
    mergeSort(input, mid, end);
    merge(input, start, mid, end);
    return;
}

public static void merge(int[] input, int start, int mid, int end) {
    if (input[mid - 1] <= input[mid]) {
        return;
    }
 //        index of "left" array
    int i = start;
 //        index of "right" array
    int j = mid;
    int tempIndex = 0;
    int[] temp = new int[end - start];

    while (i < mid && j < end) {
        temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
    }
 //        optimizes the merge. If there are elements in the left array we just copy them back
 //        into the input array instead of merging them with the temp array first
    System.arraycopy(input, i, input, start + tempIndex, mid - i);
    System.arraycopy(temp, 0, input, start, tempIndex);
    return;
}

Answer 1

从评论中可以看出一些注意事项：

• 在 Windows 中，System.currentTimeMillis()时钟精度为 64 Hz（或 15.625 ms），因此最小差异为 15 ms。
• 考虑到数组的随机初始化，它们将被部分排序，并且对部分排序的数组进行排序将比未排序的数组（稍微）快

当您添加可复制性问题时，很明显，要获得显示 O(n log n) 复杂度的合理结果，您应该：

• 用于System.nanoTime获得更精确的时钟测量。
• 使用更大的数组来扩大时间差
• 使用JMH等代码分析器/基准测试器