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?

[DoTheMath]

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

[/ QUOTE ]
The relative speeds of sort algorithms themselves are not generally affected by the size of the individual data values. The sorting algorithms are data type independent. The characteristics of the data that most affect the choice of fastest algorithm are the number of items to be sorted and the degree to which they are already sorted. Another factors is whether the sort is to be done using the memory that stores the data or whether more memory or memory structures are available to be used as an intermediate or replacement storage area. Another factor that might affect the choice of algorithms is the distribution of data within the range.

The issue of number size is more likely to affect the comparison algorithm used by the sort and the data structure of your implementation.

[ QUOTE ]

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

[/ QUOTE ]
As long as you are still sorting numbers, generally the answer is no. If the numbers are very large integers that do not fit into a numeric data type supported by your implemention environment, you may find yourself representing your data as a string of (often character) values. This might lead one to consider a LSD radix sort, but I don't believe that this would likely be faster than a comparison sort.

As oe39 said, read wiki, but I would suggest starting with the Sorting Algorithms page, or read Knuth.

[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 ]


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.