c - 挿入ソートがクイックソートに勝るポイント

Question

ソート対象の配列の長さが短い場合に挿入ソートに切り替えるクイックソートを書いています。いくつかのテストを実行したところ、ソートされる配列が 200 要素以下の場合、挿入ソートに切り替える方が高速であることがわかりました。これは非常に大きいようです。私は 20 に近いものを期待していました。基本的なウィキペディアのアルゴリズムを使用しました。

void quicksort(int list[asize], int left, int right)
{
    int pivotindex;
    int newpivotindex;

    if (left < right)
    {
            if ((right-left)<=200)
            {
            insertionsort(list,left,right);
            }
    }
    else
    {
        pivotindex = r_rand(left,right);
        newpivotindex = partition(list, left, right, pivotindex);

        quicksort(list, left, newpivotindex-1);
        quicksort(list, newpivotindex+1, right); 
    }
    return;
}

int partition(int* list,int left, int right, int pivotindex)
{
int pivotvalue = list[pivotindex];
int temp;
int i;
int storeindex;

temp=list[pivotindex];
list[pivotindex]=list[right];
list[right]=temp;

storeindex=left;

for (i=left;i<right;i++)
{
    if (list[i] < pivotvalue)
    {
        temp=list[i];
        list[i]=list[storeindex];
        list[storeindex]=temp;

        storeindex++;
    }
}

temp=list[storeindex];
list[storeindex]=list[right];
list[right]=temp;

return storeindex;
}

void insertionsort(int* list, int left, int right)
{
int i;
int item;
int ihole;

for (i=left;i<=right;i++)
{
    item=list[i];
    ihole=i;
    while (ihole > 0 && list[ihole-1] > item)
    {
        list[ihole]=list[ihole-1];
        ihole--;
    }
    list[ihole]=item;
}

return;
}