Почему моя временная сложность сортировки Шелла выглядит линейной и далеко не n^2 ⇐ C++

[Anonymous]

Мне нужно сравнить сортировку вставками и сортировку Шеллом (с разными пробелами)
Когда я пытался измерить время для сортировки вставками, все выглядело нормально (оно близко к n^2), но для сортировки Шелла с использованием пробелов Шелла результаты выглядят далеко не n^2, я знаю, что это должно быть быстрее, чем сортировка вставкой, но я не думаю, что так много ожидается, он сортирует массив, пробелы выглядят нормально, но результаты выглядят слишком быстро и линейный, чего быть не должно
Я компилирую кодовые блоки с помощью компилятора GNU GCC с -O0
#include
#include
#include
#include
#include
using namespace std;
using namespace chrono;

void InsertSort(int tab[], int n)
{
for(int i=1; i=0; j--)
{
if(tab[j]>temp)
{
tab[j+1] = tab[j];
}
}
tab[j+1] = temp;
}
}

void ShellSort(int tab[], int n, int gaps[], int gapsSize)
{
for(int g = 0; g < gapsSize; g++)
{
int gap = gaps[g];
for(int k = 0; k < gap; k++)
{
for(int i=gap+k; i=0; j=j-gap)
{
if(tab[j]>temp)
{
tab[j+gap] = tab[j];
}
else{break;}
}
tab[j+gap] = temp;
}
}
}

}

int* ShellSortGaps(int n, int& gapSize) // SHELL
{
int k=n/2;
int counter = 0;
do
{
k = k/2;
counter++;
}while(k>0);
int* gap = new int[counter];
k=n/2;
for(int i=0; i

Подробнее здесь: https://stackoverflow.com/questions/792 ... re-near-n2