On 02/08/12 14:53, Walt Brainerd wrote:
> I believe one can prove that the best sort (of the sort we are
> thinking of)
> is O(n log n).
My question was more of the practical matter...mostly asking for an
actual (tested and hopefully optimized) code and not the complexity theory.
In any case, radix sort can be O(n) because it relies on finite number
of bits used to store the numbers.
Heapsort seems to be just fine for what I needed. It is not O(n) but it
is lean on memory and I can sort as large an array as I can fit in
memory fast enough for my needs.