小编the*_*gar的帖子

我正在为我的算法类做作业，我必须证明内部合并排序的时间复杂度为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, …