マージソート（N * [N]をログ）ランタイム

Question

、我々はCでマージソート関数を記述するために、次のとおりです。

sort(int* array, unsigned len); 

私は、コードが書かれており、作業を持っていますが、そのランタイムはO(N^2*log[N])であり、これはマージソートの目的を無効にします。次のように合流部があるため、非効率理由は：

ct1左リストするためのカウンタである

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++; 
    } 
} 

をct2は、右側のリストのためのカウンタであり、アレイは、アレイへのポインタです。 ct1とct2の両方が最初にゼロに設定されます。私が言ったように、これは機能します、あなたはすべてをシフトしなければならないので、それはただ効率的ではありません。並べ替える前にサブ配列を2つの一時配列に分割したいのですが、長さが定数として定義されていない配列は作成できません。ヘルパー関数を使うことはできますが、関数のパラメータを変更することはできません。配列へのポインタと長さが必要です。

Answer 1

固定長でない配列、つまりGoogle mallocを作成できます。マージソートでは、補助メモリを使用して正しく動作する必要があります。あなたが完了したときにmallocによって割り当てられたメモリはfreeでなければなりません。