在进行合并排序时是否有必要将索引作为参数传递？

Question

我在网上看到了许多mergesort的实现，比如https://www.geeksforgeeks.org/merge-sort/传入参数l、m和r，以了解子数组的开始和结束位置。我想知道，如果我们复制子数组并将其传入，运行时和空间复杂性是否会保持不变。建议的代码示例如下：

class Solution {

    //mergeSort implementation
    public int[] sortArray(int[] nums) {

        if (nums.length == 1) {
            return nums;
        }

        int arrayLength = nums.length;

        // make copies instead of passing indices
        int[] left = Arrays.copyOfRange(nums, 0, arrayLength/2);
        int[] right = Arrays.copyOfRange(nums, arrayLength/2, arrayLength);

        left = sortArray(left);
        right = sortArray(right);

        return merge(left, right);

    }

    public int[] merge(int[] left,int[] right) {

        int[] merged = new int[left.length + right.length];

        int mergedCounter = 0;
        int i = 0; //leftCounter
        int j = 0; //rightCounter
        while (mergedCounter != left.length + right.length) {
            if (i == left.length) {
                merged[mergedCounter] = right[j];
                mergedCounter++;
                j++;
            } else if (j == right.length) {
                merged[mergedCounter] = left[i];
                mergedCounter++;
                i++;
            } else {
                if (left[i] <= right[j]) {
                    merged[mergedCounter] = left[i];
                    mergedCounter++;
                    i++;
                } else {
                    merged[mergedCounter] = right[j];
                    mergedCounter++;
                    j++;
                }
            }
        }

        return merged;

    }

}

我相信运行复杂性并没有增加，因为创建一个副本所需的运行时间与通过new int[n]初始化一个n长度的新数组所需的运行时间相同。问题的这一部分还包括一个O（n）merge子函数，所以这无关紧要。

我也相信空间的复杂性保持不变。当我们在递归调用中创建两个临时子数组时，将在合并步骤中创建与使用指向l、m和r的指针的在线解决方案中指定的相同数量的空间。

我的思考过程是有效的，还是我错过了什么？

Answer 1

任何额外的复制操作都会增加运行时间。复制子阵列将增加常量的空间需求，但由于“复杂性”忽略常量和/或低阶项，空间“复杂性”将保持不变。

大多数库使用自下而上合并排序的一些变体，其中索引（或指针）会动态更新，而不是通过递归传递，并且通常保存在基于编译器优化的寄存器中。自上而下的合并排序主要用作学习练习。

通过基于自下而上合并排序的合并过程或自上而下合并排序的递归级别更改合并方向，可以最小化复制操作。

对于C/C，传递数组和索引的替代方法是传递指针或迭代器，将每次调用所需的参数数减少1个参数。