合并排序用C与O（N *登录[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是柜台右边的列表和数组是指针数组。最初将ct1和ct2都设置为零。就像我说的那样，这样做很有效，因为你必须改变一切。我想在排序之前将子数组拆分为两个临时数组，但你应该不能创建其长度未定义为常量的数组。我还应该注意到，虽然我可以使用帮助函数，但我不能更改函数参数：必须有指向数组的指针和长度。

Answer 1

您可以创建非常量长度的数组，google malloc。合并排序需要使用辅助内存才能正常工作。当你完成它时，你必须free由malloc分配的内存。