Back to General and Gameplay Programming

Merge Sort - efficiancy crushed by recursion?

Lutrosis · 2002-01-02T19:24:47

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

General and Gameplay Programming Programming

Started by Lutrosis December 30, 2001 01:05 AM

14 comments, last by Lutrosis 22 years, 3 months ago

Shannon Barber

1,684

January 01, 2002 06:27 PM

The & 0xFF operation of the radix sort is the analog of the > operation in other sorts... no it''s not a comparison - but it''s not a fair comparison to measure a sort''s effectiveness solely by comparisons!

What are the reads/writes/compares for a merge sort?

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

Shannon Barber

1,684

January 01, 2002 06:30 PM

quote:Original post by Beer Hunter
By that logic, you could say that adding or subtracting numbers is a comparison.

If you consider the disassembly they're not all that different...
Actually, I say that a subtraction is _more like a comparison than & is
a jnz instead of a mov

Edited by - Magmai Kai Holmlor on January 1, 2002 7:32:06 PM

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

DrPizza

160

January 01, 2002 07:04 PM

Hmmm. An array of 16 bins. I do declare, I''ve just overflowed. I meant, of course, 256 bins.

char a[99999],*p=a;int main(int c,char**V){char*v=c>0?1[V]:(char*)V;if(c>=0)for(;*v&&93!=*v;){62==*v&&++p||60==*v&&--p||43==*v&&++*p||45==*v&&--*p||44==*v&&(*p=getchar())||46==*v&&putchar(*p)||91==*v&&(*p&&main(0,(char**)(--v+2))||(v=(char*)main(-1,(char**)++v)-1));++v;}else for(c=1;c;c+=(91==*v)-(93==*v),++v);return(int)v;}  /*** drpizza@battleaxe.net ***/

Beer Hunter

712

January 02, 2002 06:06 PM

"The & 0xFF operation of the radix sort is the analog of the > operation in other sorts..."

What if you use a 32-bit radix?

"no it's not a comparison - but it's not a fair comparison to measure a sort's effectiveness solely by comparisons!"

Exactly!
But that doesn't mean you should hallucinate new meanings for "comparison". It means you should be measuring other things (reads and writes) as well!

How many reads and writes are used by the merge sort? I counted them and got 39,902,848 reads and the same number of writes <edit>for a 1,000,000 element array</edit>. For the record, 2 * 1,000,000 * log2 1,000,000 = 39,863,137 (rounded)... that's less than 0.1% off.

Edited by - Beer Hunter on January 2, 2002 7:12:14 PM

Shannon Barber

1,684

January 02, 2002 07:19 PM

I said it was _like_ a comparison

Is it feasible to devise a radix sort for floating point types?

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

DrPizza

160

January 02, 2002 07:24 PM

To an extent, yes.

http://codercorner.com/RadixSortRevisited.htm

char a[99999],*p=a;int main(int c,char**V){char*v=c>0?1[V]:(char*)V;if(c>=0)for(;*v&&93!=*v;){62==*v&&++p||60==*v&&--p||43==*v&&++*p||45==*v&&--*p||44==*v&&(*p=getchar())||46==*v&&putchar(*p)||91==*v&&(*p&&main(0,(char**)(--v+2))||(v=(char*)main(-1,(char**)++v)-1));++v;}else for(c=1;c;c+=(91==*v)-(93==*v),++v);return(int)v;}  /*** drpizza@battleaxe.net ***/

Merge Sort - efficiancy crushed by recursion?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Merge Sort - efficiancy crushed by recursion?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines