Need help making Merge Sort run faster.

[mfswimmer]

Hi, I have written a merge sort algorithm that used vectors how ever it runs rather slowly. I believe it has to do with the fact I'm creating two vectors everytime order trades is called but I'm not sure. I also cannot change the parameters in ordertrades. Thanks in advance.

[Peter87]

You can probably gain a lot by not creating new vectors all the time and instead use indices and reuse the same vector but I don't sure what is possible. In merge you can get rid of the erase calls by using two indices to keep track of where in A and B you are.

[shacktar]

Erasing from the beginning of a vector has a large performance penalty as the whole vector from index 1 to to size() - 1 has to be shifted. Just keep track of the current index for A and B and increment the appropriate one when you merge from that vector.

[mfswimmer]

Hey guys thanks for your responses. I attempted to use indices however it crashes. I'm not sure how to call the function recursively though with indices involved. Here's what I changed.

[shacktar]

First, I would leave orderTrades the way you had it originally, and just fix the erase(vector.begin) issue in merge.

[mfswimmer]

I did that and it had speed up slightly but still appears sluggish.

[Peter87]

Did you fix line 19 in your code?

How many elements are you sorting and what times are we talking about?

[mfswimmer]

oh yea I saw that after I posted the code, I'm not sure about the number of elements since that part was not written by me however it was about a minute with my original code and after doing your suggestion It became about 30 seconds.

[Peter87]

I don't think it makes much different but you can try to put tempC.reserve(A.size()); after line 3.

[mfswimmer]

Thanks guys for the help so far. So far this is what I have, and its runetime has decreased significantly from about a minute to 20ish seconds. Not sure what else I can do though.

[Peter87]

Replace line 37-45 with

vector<FoodSource*> tempA(trades.begin(), trades.begin() + middle);
vector<FoodSource*> tempB(trades.begin() + middle, trades.end());

[shacktar]

You can try passing in trades by reference to merge. That way, you don't have to create a tempC vector and have to copy it back to trades. The size of trades is guaranteed to be A.size() + B.size() so the changes to the body of merge would be minimal. If that doesn't speed things up significantly, then you can experiment again with an in-place merge sort. (But apparently from what I've gathered, in-place merge sort is not trivial to implement).

[bluecoder]

But i have a question .. will this code of mfswimmer sort correctly .. i came to this doubt e.g
if there are 10 element in the array .. first 5 will be sorted ... (top 5 ) and then ( next 5 ) and lastly whole ten element .. but ... seems confusing .. sorry for my lack of knowledge .. please clear me ...

[Gaminic]

It doesn't just sort left half, right half, total. It works recursively.

http://en.wikipedia.org/wiki/Merge_sort

[bluecoder]

thanks ...Gaminic ..it helped ..

[mfswimmer]

Thanks all for your suggestions I was able to get the runetime from about a minute to 12 seconds. Thanks again