Invisible <voi### [at] devnull> wrote:
> Trouble is, both quick-sort and merge-sort are recursive algorithms, and 
> to implement them on tape would require an unbounded number of tapes, 
> which isn't really practical.

  I don't think you understand how merge sort works. Merge sort is exactly
what you are looking for in this case (ie. you want to sort a large amount
of data in a slow storage medium, and you have a secondary empty storage
medium of the same size to use for the sorting).

  Each pass of the merge sort will copy all the data from one tape to the
other, alternatively. The total amount of such copyings will be exactly
ceil(log2(n)) (where n is the amount of elements to sort). For example,
if the amount of elements to sort is 10 billions, merge sort will require
to copy all the data from one tape to the other exactly 34 times. Only
two elements need to be in RAM at a time.

  You can reduce the number of copyings by sorting smaller partitions in
RAM (in other words, instead of sorting partitions of 2 elements in the
first merge sort pass and writing the result to the second tape, you
sort partitions of as many elements as will fit in RAM before writing
the result to the second tape). For example, if you can sort 1 million
elements in RAM, you will save log2(10^6) = 19 copyings, so the total
number of times you need to copy all the data from one tape to the other
is reduced to 15.

  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.

-- 
                                                          - Warp

Post a reply to this message