c - 合并排序在 C 与 O(N*log[N]) 运行时

Question

对于一个赋值，我们要用 C 语言编写归并排序函数:

sort(int* array, unsigned len);

我已经编写并运行了代码，但它的运行时间是 O(N^2*log[N])，这违背了归并排序的目的。效率低下的原因是因为合并部分如下:

while(ct1 < len1 && ct2 < len2){
    if(array[0] < array[len1 - ct1]){
        ct1++;
        array++;    // no longer look at that element
    }
    else{
        int position = len1 - ct1;
        int hold = array[position];
        while(position > 0){
            array[position] = array[position - 1];
            position--;
        }
        array[0] = hold;
        ct2++;
        array++;
    }
}

其中 ct1 是左列表的计数器，ct2 是右列表的计数器，array 是指向数组的指针。 ct1 和 ct2 初始设置为零。就像我说的，这行得通，只是效率低下，因为你必须改变一切。我想在排序之前将子数组拆分为两个临时数组，但你不能创建长度未定义为常量的数组。我还应该注意，虽然我可以使用辅助函数，但我不能更改函数参数:必须有一个指向数组的指针和长度。

Answer 1

您可以创建长度不固定的数组，google malloc。合并排序需要使用辅助内存才能正常工作。完成后，您必须释放 malloc 分配的内存。