Почему эти две версии быстрой сортировки дают резкие различия в количестве сравнений?

У меня есть две разные реализации быстрой сортировки ниже. Я проверил, что одна из этих версий быстрой сортировки работает в том смысле, что они будут сортировать любой массив, который я ему предоставлю. Если вы заметили (по крайней мере, мне кажется), версия # 2 точно такая же, как версия # 1, когда размер массива n больше 8. Следовательно, я ожидал бы, что когда я дам обеим этим функциям массив одинакового размера, который больше 8, они должны в среднем проводить примерно одинаковое количество компонентных сравнений, но это не так.

За n > 8обе функции используют sort3() а также partition() функции. Я перечислил и те, что ниже, чтобы показать вам, как я считаю количество компонентных сравнений.

я знаю это W(n)теоретическое число сравнений наихудшего случая для этих реализаций быстрой сортировки составляет (n (n + 2) / 4) +8. Поэтому для размера массива n = 500, W(n) = 62758, Для пробного запуска на массиве размера n = 500Версия # 1 делает в среднем около 5000 сравнений, что вполне разумно. Тем не менее, версия № 2 делает в среднем 80000 сравнений. Очевидно, что это не может быть правдой — версия №2 делает больше сравнений, чем теоретическая W(n) и это точно (по крайней мере, мне кажется) тот же алгоритм, что и версия # 1.

Вы видите ошибку, которую я делаю в версии # 2?

Версия № 1:

void Quicksort_M3(int S[], int low, int hi)
{
if(low < hi)
{
if((low+1) == hi)
{
comparisons++;
if(S[low] > S[hi])
swap(S[low],S[hi]);
}
else
{
Sort3(S,low,hi);
if((low+2)<hi)
{
swap(S[low+1],S[(low+hi)/2]);
int q = partition(S, low+1, hi-1);
Quicksort_M3(S, low, q-1);
Quicksort_M3(S, q+1, hi);
}
}
}
}

Версия № 2:

void Quicksort_Insert_M3(int S[], int n, int low, int hi)
{
if((hi-low)<=8)
Insertionsort(S,n);
else
{
if(low < hi)
{
if((low+1) == hi)
{
comparisons++;
if(S[low] > S[hi])
swap(S[low],S[hi]);
}
else
{
Sort3(S,low,hi);
if((low+2)<hi)
{
swap(S[low+1],S[(low+hi)/2]);
int q = partition(S, low+1, hi-1);
Quicksort_Insert_M3(S, n, low, q-1);
Quicksort_Insert_M3(S, n, q+1, hi);
}
}
}
}
}

Раздел:

int partition(int *S,int l, int u)
{
int x = S[l];
int j = l;
for(int i=l+1; i<=u; i++)
{
comparisons++;
if(S[i] < x)
{
j++;
swap(S[i],S[j]);
}

}
int p = j;
swap(S[l],S[p]);
return p;
}

Sort3:

int Sort3(int list[], int p, int r)
{
int median = (p + r) / 2;
comparisons++;
if(list[p] <= list[median])
{
comparisons++;
if(list[median]>list[r])
{
comparisons++;
if(list[p]<list[r])
{
int temp = list[p];
list[p] = list[r];
list[r] = list[median];
list[median] = temp;
}
else
{
exchange(list,median,r);
}
}
else
;

}
else
{
comparisons++;
if(list[p] > list[r])
{
comparisons++;
if(list[median] < list[r])
{
int temp = list[p];
list[p] = list[median];
list[median] = list[r];
list[r] = temp;
}
else
{
exchange(list,p,r);
}
}
else
{
exchange(list,p,median);
}

}return list[r];
}