c++ - 无法将合并排序设为 O(n log n)

Question

坦白说，我是一名学生，在合并排序方面遇到了麻烦。目的显然是要有一个 O(n log n)，但它更多的是 n^2。我认为问题出在 tempList 中，正如您将在代码中看到的那样，但在程序描述中它说要使用 static int tempList[LIST_SIZE] 来避免降级。

这是我所拥有的，使用 start 的运行时约为 16000，这显然是合并排序的一种方式。

    void mergeSort(int randomNum[], int lowIdx, int highIdx)
    {
        int midIdx;

        if (lowIdx < highIdx)
        {
            midIdx = (highIdx + lowIdx) / 2;
            mergeSort(randomNum, lowIdx, midIdx);
            mergeSort(randomNum, midIdx + 1, highIdx);
            merge(randomNum, lowIdx, midIdx, highIdx);
        }
    } 

这是排序的第二部分

    void merge(int randomNum[], int lowIdx, int midIdx, int highIdx)
    {
        static int tempList[MAX_SORT];

        for (int count = 0; count <= highIdx; count++)
            tempList[count] = randomNum[count];

        int leftIdx = lowIdx,
        rightIdx = midIdx + 1,
        tempPos = lowIdx;

        while (leftIdx <= midIdx && (rightIdx <= highIdx))
        {
            if (tempList[leftIdx] <= tempList[rightIdx])
            {
                randomNum[tempPos] = tempList[leftIdx];
                leftIdx++;
            }
            else
            {
                randomNum[tempPos] = tempList[rightIdx];
                rightIdx++;
            }
        tempPos++;
        }

        while (leftIdx <= midIdx)
        {
            randomNum[tempPos] = tempList[leftIdx];
            tempPos++;
            leftIdx++;
        }

        while (rightIdx <= highIdx)
        {
            randomNum[tempPos] = tempList[rightIdx];
            tempPos++;
            rightIdx++;
        }
    }

程序的细节是我们有一个包含 100000 个随机数的数组，并使用各种排序算法对其进行排序。其他类型按预期工作，但与 big-O 的预期相比，这个似乎有很大差距。

有人可以帮忙吗？

Answer 1

不确定这是否是您的全部问题，但这是一个问题:

您正在将 randomNum 复制到 tempList，从 0 到 highIdx，但您只能访问 tempList 从 lowIdx 到 highIdx。

这意味着您从 0 复制到 lowIdx 的所有项目都是浪费的拷贝。

解决方案:只复制你需要的。

for (int count = lowIdx; count <= highIdx; count++)