大きな配列ではC++の挿入ソートが機能しません

Question

私のinsertionSort関数は小さな配列では機能しますが、50,000個のランダムな値を持つ配列では機能しません。私はこれを理解しようと時間を費やしましたが、私は困惑しています。ここでは、コードは次のようになります。

void insertionSort(int array[], int length) { 
    int swapHolder, counter, index; 
    for (counter = 1; counter < length; counter++) { 
     index = counter; 
     while (counter > 0 && array[index - 1] > array[index]) { 
       swapHolder = array[index]; 
       array[index] = array[index - 1]; 
       array[index - 1] = swapHolder; 
       index--; 
     } 
    } 
} 

私の他のソート機能（バブルソート）は、大規模な配列のために正常に動作しますが、私はこの問題にハングアップしています。

Answer 1

ライン

while (counter > 0 && array[index - 1] > array[index]) { 

が深くノートで

while (index > 0 && array[index - 1] > array[index]) { 

である必要があり、それは小さな配列に最適なように、挿入ソートの平均複雑さはO(n^2)です。つまり、50,000の値をソートするのは正しいアルゴリズムではありません。