Algorithm needed: reading/writing a large file

[Kenneth Almquist]

jwp at larry.sal.wisc.edu (Jeffrey W Percival) writes:
> I am writing a C program (Ultrix, VAXstation 2000) to re-arrange a
> large disk file.  The file contains a large number of fixed length
> records.  [The program sorts the keys in memory, and then does
> random accesses to the file to write the records in order.]
>
> I cannot have all of [the file] in memory, but can have more than the one
> record I am currently using in this shuffle.  How can I speed this up?

I'm pretty sure that you can't speed up a shuffle operation much by
keeping only part of the data in memory.  Anyone with a theoretical
bent want to try to prove this?

I suggest you try the traditional approach of sorting chunks of the
file in memory and then merging the results.  This will perform more
I/O than your scheme, but it will be sequential I/O.
				Kenneth Almquist