>> 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.

I used it a long time ago for sorting triangles based on depth (before depth 
buffers).  For a tape drive system I would sort 1 bit at a time to minimise 
the number of passes, and using 4 tapes instead of 2 you could probably 
avoid reading the input twice for each bit.  This algorithm Might Work (it 
can probably be adapted for non-integer data somehow):

4 tapes:
input1 = input data
input2 = empty or some more input data
output1 = empty
output2 = empty

for b = 0 to <max bits in data>

 while not eof(input1)
  n = read next from input1
  if bit b of n is not set,
    write n to output1
  else
    write n to output2
 endwhile

 rewind input1
 // next loop can run whilst input1 is rewinding

 while not eof(input2)
  n = read next from input2
  if bit b of n is not set,
    write n to output1
  else
    write n to output2
 endwhile

 rewind input2
 rewind output1
 rewind output2

 wait until all tapes rewound

 swap input1,output1
 swap input2,output2

next

Post a reply to this message