>> Depending on what type of data you want to sort and the seeking
>> characteristics of a tape drive, a radix sort might work quite well.
>> Just an idea.
>
> I don't actually know how that works. I'll have to go look it up.

Having read the article on radix sort, it appears that it's similar to a 
quick-sort or bucket sort, except that you split the input into several 
output buckets based on the "digits" of the key, rather than on comparisons.

This results in the processing time being proportional to the number of 
digits in the key and independent of the actual number of keys to process.

One immediate and obvious problem is that the buckets might fill very 
unequally, depending on the distribution of the data to be sorted. (This 
is essentially the same problem that quick-sort has.)

In contrast, a merge-sort takes exactly the same amount of time 
regardless of what the data *is*. The sorting time depends only on *how 
much* data there is.

I'm still leaning towards merge-sort (especially since the data I'm 
thinking about sorting is floating-point numbers). But I guess what I 
need to do is run some simulations...

Post a reply to this message