Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Lutrosis

Merge Sort - efficiancy crushed by recursion?

This topic is 6017 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m doing an assignment for a c++ class which involves implementing a number of sorting algo''s, and then benchmarking them and writing up a little comparison. The first two I did were MergeSort and BubbleSort, and I''m getting odd results. MergeSort is supposed to be a pretty efficient sort, especially compared to bubblesort. Yet Bubblesort is coming up very significantly faster in my benchmarks. Here are some example results, sorting sets of integers (the same set of data was sorted for both sorts): Merge Sort ---------------- Sorted 10000 elements. Took 120436 compares. Took 4.17558 seconds. Bubble Sort ---------------- Sorted 10000 elements. Took 24781373 compares. Took 3.08413 seconds. The compare values are a bit deceptive - they count only comparisons between two integers. So for MergeSort, a significant amount of looping in the section of code that merges arrays isn''t really factored in. They still provide a pretty good idea of the efficiency of the sorts as far as loops. And yet the times are completely different from what I''d expect. The timing code is correct, I checked it out already. I''m using QueryPeformanceCounter and QueryPerformanceFreq to calculate times, so I can get very accurate measurements. The only thing I can think of that''s slowing down MergeSort is the fact that it''s recursive, and so it makes a *ton* of function calls. Perhaps the overhead from all the calls is what''s creating the horrific slowdown? Here''s the main MergeSort function, excluding the Merge function (which I can post if necessary): void MergeSort(unsigned int theArray[], unsigned int start, unsigned int end) { if (start

Share this post


Link to post
Share on other sites
Advertisement
Hmm... Post code in source blocks so that < and > don''t break everything.

I have a guess as to the problem, but I can''t confirm it as you didn''t post all of your code. I''m betting the problem is in your merge routine. I suspect you''ve either got a merge that runs in more than O(n) time, or else you''re using a merge that doesn''t work in place, and you''re allocating new arrays every time you go into the merge function.

Share this post


Link to post
Share on other sites
Sorry about the ambiguity. Here's the routines I'm using for my merge sort:

    
void MergeSort(unsigned int theArray[], unsigned int start, unsigned int end)
{
if (start<end)
{
int split=(start+end)/2;
MergeSort(theArray, start, split);
MergeSort(theArray, split+1, end);
Merge(theArray, start, end, split);
}
}


void Merge(unsigned int theArray[], unsigned int start, unsigned int end, unsigned int split)
{
unsigned int Temp[MAX_ARRAY];
unsigned int index=start, tracer1=start, tracer2=split+1;


while (tracer1 <= split && tracer2 <= end)
{
NumComps++;
if (theArray[tracer1] < theArray[tracer2])
Temp[index++]=theArray[tracer1++];
else
Temp[index++]=theArray[tracer2++];
}

while (tracer1 <= split)
{
Temp[index++]=theArray[tracer1++];
}
while (tracer2 <= end)
{
Temp[index++]=theArray[tracer2++];
}

// move everthing back

index=0;
for (index=start;index <= end;index++)
{
theArray[index]=Temp[index];
}


return;
}


I think the Merge() routine should be ok, its not terrifically efficiant, but it ought to work alright. I just never realized that recursive function calls could have such an impact. Looks like I need to come up with a non-recursive version Unless I'm missing something and this can be speeded up?


*** EDIT ***

Well, looks like that problem's solved. I apologize, I wasn't thinking. I made those local variables in Merge() global, and here are the results:


Merge Sort
----------------
Sorted 10000 elements.
Took 120381 compares.
Took 0.0332993 seconds.


Bubble Sort
----------------
Sorted 10000 elements.
Took 25231498 compares.
Took 3.097 seconds.


So much for that problem Thanks for your help guys!

-Lutrosis

Edited by - Lutrosis on December 30, 2001 1:29:53 PM

Share this post


Link to post
Share on other sites
For your sorting demo, I recommend that you demonstrate at least the following sorts:

bubble sort, insertion sort, selection sort, shell sort, merge sort, heap sort, quicksort, radix sort

Java source for all those sorts (except the radix sort) can be found here (it also has several other sorts.). Information on the radix sort can be found here.

I also ran a quick test...

Merge Sort
----------
Sorted 1000000 elements.
Took 18674991 compares.
Took 1.956463 seconds.

Radix Sort
----------
Sorted 1000000 elements.
Took 0 compares.
Took 0.692400 seconds.

Share this post


Link to post
Share on other sites
com·par·i·son (n.)

1)
    a) The act of comparing or the process of being compared.
    b) A statement or estimate of similarities and differences.
2) The quality of being similar or equivalent; likeness: no comparison between the two books.
3) Grammar. The modification or inflection of an adjective or adverb to denote the positive, comparative, and superlative degrees, as in English, along with the equative degree in certain other languages, such as Irish Gaelic.


Share this post


Link to post
Share on other sites
quote:
Original post by Stoffel
not to be a nit-picker, but moving a value to a bin indexed by its value in radix N is a comparison IMHO. =)

Not so.

Consider, I have an array of 16 bins and I''m sorting 4 byte integers, and each bin has an addElement() method to add the current element to its elements (be they a linked list, array, vector, whatever; arrays and vectors give constant-time insertions but ideally require you to know how big each bin will be before creating them. A lookaside list might be a good compromise).

I''m sorting first by the lowest byte:
  
bin[(e & 0xff)].addElement(e);

sorting for the higher bytes works similarly.

I don''t have to compare the value of that byte to anything, I can simply use it as an offset into the array.

Share this post


Link to post
Share on other sites
Wow! I can sort a list of ANY SIZE in O(0) time with a radix sort!!!!


A radix sort may not "compare" two elements the same way most other sorts do, but for the purposes as a measurable you need to count something... Change the measurable to memory accesses instead of compares if you want.

e&0xFF is like a comparison - at least count those if you keep counting compares.

Share this post


Link to post
Share on other sites
(implementation specific)

Radix Sort
----------
Sorted 1000000 elements.
Took 0 compares.
Took 8000000 reads.
Took 4000000 writes.
Took 0.692400 seconds.


Happy?

The use of the operator & ... a comparison? By that logic, you could say that adding or subtracting numbers is a comparison. And since the dereferencing of arrays requires addition, every time you dereference the array, it''s a comparison!

Maybe those are all comparisons by a stretch of the imagination, but by "comparison", we mean a comparison between two elements in the sorting array, not some other number.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!