C++ inserting sort не работает для больших массивов

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

Моя другая функция сортировки (BubbleSort) отлично работает для больших массивов, но я повесил трубку, по этому вопросу.

Answer 1

Линия

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

должен быть

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

На более глубоком примечании, средняя сложность для вставки рода есть O(n^2) так, что она работает лучше всего для небольших массивов. То есть, это не правильный алгоритм для сортировки 50 000 значений.