CODEWITHSUNDEEP
c++algorithmsortingmergesortinsertion-sort
AerRayes
AerRayes

Reputation: 69

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.

Upvotes: 1

Views: 2669

Answers (4)

Swarup Hegde
Swarup Hegde

Reputation: 1

Merge sort is not necessarily slower than an insertion sort. Time take by insertion sort to sort 'n' items is proportional to n squared (nn) while the time taken by merge sort is proportional to n times log of n base 2 (nlgn) So insertion sort is faster than the merge sort in some code while merge sort in others

Upvotes: 0

Denes
Denes

Reputation: 21

Apart from the mrip answer about references, keep in mind:

"Insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort. The best case input is an array that is already sorted. In this case insertion sort has a linear running time. The simplest worst case input is an array sorted in reverse order."

Upvotes: 0

mrip
mrip

Reputation: 15163

Passing vectors by reference rather than by value makes a huge difference. On my machine with SIZE=50000, compiled with -O3, before:

merge sort time = 5730000

insertion sort time = 1470000

After:

merge sort time = 10000

insertion sort time = 1470000

I only changed two lines:

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

Upvotes: 3

lolando
lolando

Reputation: 1751

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

Upvotes: 1

Related Questions