AerRayes - 6 days ago 8
C++ Question

# 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.