Re: Best Sorting Algorithm For Large Numbers
[ 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?
|