On 12/10/2010 05:06 PM, Warp wrote:

>    Merge sort requires a lot of seeking when comparing partitions. However,
> you can use the RAM to reduce the needed amount of seeking by reading as
> many elements of each partition being compared as possible to RAM, and
> then doing the comparisons in RAM and writing the result to the other
> tape. There will still be a fair amount of seeking (in the tape being
> read), but this RAM buffering will reduce it quite significantly.

And if you put half of the data onto one tape and half of the data onto 
another tape, you can avoid *all* of the tape seeks. Each 
partially-sorted "chunk" is the same as all the others; you don't need 
to keep them arranged with respect to each other. So on each pass, just 
write half of the chunks onto one output tape and half onto the other. 
Then rewind the tapes and merge from both input tapes (again onto two 
output tapes). In this manner, with 4 tapes, you need no tape seeks at 
all. (The number of passes is of course still log N.)

Post a reply to this message