Best Sorting Algorithm For Large Numbers

[gaming_mouse]

It's been a while since I used sorting algorithms.... so I figured I'd get a good answer here.

If you had to sort a list of random numbers between 0 and 9999999999999999 (16 digits), what is the fastest algorithm?

If the maximum number changes even higher to something that does not fit in a long data type, does the answer change?

Thanks,
gm

[adios]

It's been awhile since I've delved into sorting algorithms but if memory serves you want an "n log n" algorithm for faster sorts as opposed to an "n squared" algorithm.

[CrayZee]

Fastest is a little vague, since you can consider worst case, avg case, etc (sometimes they are the same). Different sorting algorithms also have differing memory requirements, O(1), O(log n), etc. So that should also be taken into consideration if you have large data sets.

Quicksort is the brain dead choice of programmers.

[Siegmund]

As far as algorithm efficiency, yes, quick sort or one of the nearly equivalent O(n log n) methods.

As far as whether the numbers fit into a Long or not... you will want to investigate whether String or Long or user-defined "VeryLong" variants are fastest. You may get faster performance with string comparisons (pad numbers with leading zeros as necessary.)

Ultimately, however, the length of the strings has almost nothing to do with the time needed for the comparison, only with the read and write time for swapping the strings around. The "quick sort" idea of sorting sub-sub-groups and sub-groups first can be adapted to "look at only one bit at a time, and sort into groups based on whether that bit is a 0 or a 1": there is absolutely no reason to compare an entire long string against another entire long string except convenience of programming.

[oe39]

the comparison sort wikipedia page might be of interest?

[CrayZee]

Yeah, not a bad idea. I also forgot about stability issues since it's been awhile...but most sorting algorithms are pretty stable.

A quick Googling dug this up. Maybe you'll find that useful assuming it's accurate.

Specialized sorting algorithms might be faster, but Quicksort is usually good enough. It's fast enough for most purposes and won't blow up on you most of the time. Man hours are more expensive than computing hours esp. if you're solving simple business problems, etc.

gaming_mouse, what are you trying to do? Homework, something real, or pondering sorting theory?

[Wyman]

In what context are you sorting?

Is it a one-time sort? Do you want to maintain the sorted list and add/delete items over time? Are there 10000000 elements that you're sorting? 10? 2? Does your data have any structure at all, or are the numbers chosen uniformly at random from 0 to 9999999999999999?

Quick answer: For a specific problem, I'd implement and test a few sorting algorithms to see which is fastest. Check out quicksort and radix sort.

[Yobz]

"Fastest" time-complexity wise with lots of numbers and bound range would be Radix Sort, assuming no previous knowledge of data being sorted (which allows more special case sorting).

[gaming_mouse]

[ QUOTE ]
"Fastest" time-complexity wise with lots of numbers and bound range would be Radix Sort, assuming no previous knowledge of data being sorted (which allows more special case sorting).

[/ QUOTE ]

Wyman,

I read this quote from the radix wikipedia entry:

When an LSD radix sort processes keys which all have the same fixed length, then the upper bound of the execution time is O(n), where n is the number of keys to be sorted. When processing fixed-length keys, some implementations of LSD radix sorts are slower than O(n · log n) comparison-based sorting algorithms, such as heap sort, unless a sufficiently large amount of input data is processed. What a sufficiently large amount of input data precisely is will vary from computer system to computer system and from implementation to implementation.

It is not clear to me what conditions make the radix better than quicksort or heapsort exactly. Could you explain this?

[gaming_mouse]

[ QUOTE ]


gaming_mouse, what are you trying to do? Homework, something real, or pondering sorting theory?

[/ QUOTE ]

A friend of mine who's in college asked me about it... I think it was a homework assignment, yes. Anyway, I was trying to help him and I realized I wasn't sure of the answer, so I got curious.