what is the absolute FASTEST way to sort a bunch of integers?

Question

I need to be able to sort 1 million integers faster then quicksort. The fastest. I get extra points if it only takes "a[range]" executions.

Answer 1

There is a faster algorithm than O(n log n) time. The downside is that it requires memory that scales with the range of the integers.

The algorithm is called "bucket sort" on wikipedia, and it actually only takes O(n) executions if you use buckets of size 1. The downside, as I said, is that you would need to have one bucket for every integer in the range you're looking at: if your range is from 1 to 1 million, you need an array 1 million long, which shouldn't be a problem. However, if the integers are between 0 and 2^32 -1 (the range of general integers), you're not going to have enough memory to make an array that big. This answer would still be technically right, but I doubt a program that needs an array 4 GB large would be considered viable.

Answer 2

mergesort and quicksort as two algorithms which sort in O(n log n) time which on average it doesn't come any faster. There is one point to note though that these algorithms can dissolve into linear time for some data sets

Answer 3

challenging matter. seek on yahoo and bing. that will may help!