关于快速排序和归并排序的速度问题

Question

#include
#include
#include
void mergerarray(int* src,int* tem,int start,int end)
{
int mid=(start+end)/2;
int l=start,k=start,r=mid+1;
while((l {
if(src[l] tem[k++]=src[l++];
else
tem[k++]=src[r++];
}
while(l tem[k++]=src[l++];;
while(r tem[k++]=src[r++];
for(l=start;l src[l]=tem[l];
}
void mergersort(int* src,int* tem,int start,int end)
{
if(start {
mergersort(src,tem,start,(start+end)/2);
mergersort(src,tem,(start+end)/2+1,end);
mergerarray(src,tem,start,end);
}
}
void quicksort(int* src,int start,int end)
{
int l=start,r=end;
int key=0;
if(start>=end)
return;
key=src[l];
src[l]=src[(start+end)/2];
src[(start+end)/2]=key;
while(l {
while((l r--;
if(l src[l++]=src[r];
while((l=src[l]))
l++;
if(l<r)
src[r--]=src[l];
}
src[l]=key;
quicksort(src,start,l-1);
quicksort(src,l+1,end);
}
int main(void)
{
int* src=NULL;
int* tem=NULL;
int n=10000000;
int i=0;
clock_t start,end;
double duration;
src=(int*)malloc(n*sizeof(int));
tem=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
src[i]=rand();
start=clock();
//////////////排序/////////////////////////////////
// mergersort(src,tem,0,n-1);
quicksort(src,0,n-1);
////////////////////////////////////////////////
end=clock();
duration=(end-start)*1000/CLOCKS_PER_SEC;
printf("耗时%f毫秒\n\n",duration);
free(src);
free(tem);
return 0;
}

                 快速排序（ms）   归并排序（ms）

1百万数据 141 187
1千万数据 4119 2262

当排序的数据量不大时，快排的速度大于归并排序，
当排序的数据比较大时，归并排序的速度大于快排，
是不是cache命中率的原因
哪位大神可以解释一下

Answer 1

如果数据是基本有序的，那么归并更快一点不奇怪。也可能是cache的原因。要用性能热点分析工具才知道