Quicksort странные результаты?

Я совсем недавно узнал quicksort, Я читал, что выбор сводки играет очень важную роль в общей производительности.
У меня было задание, где я должен был протестировать 3 варианта выбора опорных точек — рандомизированный, медиана трех и медиана медиан на различных входных размерах.
Я читал, что версия медианы медиан не будет работать в O (n2) даже в худшем случае. Но в моих результатах, рандомизированная и медиана трех версий дала почти одинаковые результаты, медиана трех показала несколько лучшие результаты, но медиана медианов работает очень плохо на несколько порядков. Например, при входном размере 50000 рандомизированная версия работала в 16547 us в то время как медиана побежала в 1139168 us,
Может кто-нибудь объяснить, почему это происходит? (Насколько я знаю, я реализовал алгоритм выбора сводной диаграммы, правильно разбивая массив на наборы по 5, беря медиану каждого набора и снова делая это рекурсивно, пока не получу медиану.) Я что-то делаю неправильно?

Редактировать: я перепроверяю код на всякий случай, но нормально ли, что медиана реализации медиан работает так же медленно или даже медленнее (хотя бы незначительно), чем две другие реализации, или она гарантированно будет работать намного быстрее?

Edit2: вот код, который я использую для нахождения медианы медиан, значение, которое он находит, возвращается в функцию быстрой сортировки для использования в качестве точки разворота. Я уверен, что код нарушает все хорошие практики кодирования, пожалуйста, приписывайте это моей нубистской натуре и попробуйте выйти за ее пределы.

int getpivot(int arr[], int low, int high) {

int i,j,k,l,val,med[MAX/4],temp[6],pivot,mi,index,temp2;
if(high-low+1<=5) { //returns median if size of array<=5
for(i=1;i<=high;i++) {
val=arr[i];
j=i-1;
while(j>=0 && val<arr[j]) {
arr[j+1]=arr[j];
j--;
}
arr[j+1]=val;
}
return arr[(low+high)/2];
}

mi=0;
// divide array into groups of 5,
//finds median of those groups by insertion sorting
//adds these medians to med array
for(i=low;i+5<=high;) {
index=0;
for(j=i;j<i+5;j++)
temp[index++]=arr[j];
i+=5;
for(k=1;k<5;k++) {
val=temp[k];
l=k-1;
while(l>=0 && temp[l]>val) {
temp[l+1]=temp[l];
l--;
}
temp[l+1]=val;
}
med[mi++]=temp[2];
}//choose random index as pivot and partition the med array
pivot=rand()%mi;
i=low=0;
j=high=mi-1;

while(i<j) {
while(i<high && med[i]<=med[pivot]) i++;
while(med[j]>med[pivot]) j--;
if(i<j) {
temp2=med[i];
med[i]=med[j];
med[j]=temp2;
}
}
temp2=med[j];
med[j]=med[pivot];
med[pivot]=temp2;

//j is final position of pivot
//see if j is left/right or equal to the position of true median of median
// and recurse accordingly

low/=5;
high/=5;
if(j==(low+high)/2) return med[j];
else if(j<(low+high)/2) return getpivot(med,j+1,high);
else return getpivot(med,low,j-1);

}