AerRayes - 8 months ago 51

C++ Question

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.

Answer Source

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