c++ - 为什么我的合并排序代码比插入排序慢

Question

我一直在尝试进行归并排序和插入排序，并比较两者的时间结果。 并且从数组输入大小 10 到 10000 合并排序一直比插入排序慢

这是插入排序的代码

vector<int> insertion_sort(vector<int> vec)
{
    for(int i = 1 ; i <vec.size();i++)
    {
        int j = i-1;
        while(j>=0 && vec[j+1]<vec[j] )
        {
            int x = vec[j+1];
            vec[j+1] = vec[j];
            vec[j--] = x;
        }
    }
    return vec;
}

这是合并排序代码

vector<int> merge(vector<int> left,vector<int> right)
{
    int i = 0;
    int j = 0;
    vector<int> ret(left.size()+right.size());
    int it = 0;
    for(; i <left.size() && j<right.size();)
    {
        if(left[i]<right[j])
            ret[it++]=(left[i++]);
        else if(right[j]<left[i])
            ret[it++]=(right[j++]);
        else ret[it++]=(left[i++]),ret[it++]=(right[j++]);
    }
    for(;i<left.size();)
        ret[it++]=(left[i++]);
    for(;j<right.size();)
        ret[it++]=(right[j++]);
    return ret;
}
vector<int> merge_sort(vector<int> A,int start,int end)
{
    if(start >= end) 
    {
        vector<int> v(1);
        v[0]=(A[start]);
        return v;
    }
    int mid = (start+end )/ 2;
    vector<int> left = merge_sort(A,start,mid);
    vector<int> right = merge_sort(A,mid+1,end);
    return merge(left,right);
}

最后这就是我调用它们并计算时间的方式

int main()
{
    vector<int> rand_vec;

    srand(time(0));
    for(int i = 0 ; i <SIZE;i++)
    {
        rand_vec.push_back(rand()%SIZE);
    }
    int t = clock();
    vector<int> merge_sorted = merge_sort(rand_vec,0,rand_vec.size()-1);
    puts("");
    printf("merge sort time = %d\n",clock() - t );


    t = clock();
    vector<int> insertion_sorted = insertion_sort(rand_vec);
    puts("");
    printf("insertion sort time = %d\n",clock() - t );
    return 0;
}

我想知道我是否在该代码中做错了什么，使合并排序的时间比插入排序的时间多。

谢谢。

Answer 1

通过引用而不是通过值传递 vector 会产生巨大的差异。在我的机器上，SIZE=50000，用 -O3 编译，之前:

merge sort time = 5730000

insertion sort time = 1470000

之后:

merge sort time = 10000

insertion sort time = 1470000

我只改了两行:

vector<int> merge(const vector<int> &left,const vector<int> &right)
vector<int> merge_sort(const vector<int> &A,int start,int end)