Search code examples
c++algorithmsortingmergesortinsertion-sort

Why is my merge sort code slower than insertion sort


I've been trying to make merge sort and insertion sort and comparing the time result for both of them. And from array input size 10 to 10000 merge sort has been slower than insertion sort

this is the code for insertion sort

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;
}

And this is the Merge sort code

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);
}

and finally this is how I call all of them and calculate time

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;
}

I want to know if I did something wrong in that code to make the time for merge sort more than the time used in insertion sort.

Thanks.


Solution

  • to summarize the answers provided so far:
    - use reference (or pointer ) to avoid copying vectors:
    - use reserve when you know the size in advance, before using thousands of push_back (so that you do not need to reallocate dynamically whenever the capacity is exceeded)
    - you can do const vector<int>& merge_sorted = ... to avoid copy when returning your vector