Algorithm needed: reading/writing a large file

[Jeffrey W Percival]

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.  My current method is this: read through the file, building 2
arrays in memory:  array1 is an array of some attribute I want to sort
on, and array2 is just array of ascending integers (record numbers in
the first file).  Then I sort array1, with array2 tracking the
movements in array1.  I end up with array2 being a mapping of record
numbers between the input file and the sorted file.  Finally, I loop
through array2 doing a read on file1, record array2[i] and writing to
file2, record i.

Now, I'm not looking for help in the sorting of array1;  my sorting
algorithm is fast and efficient.  What is taking a long time are the
quasi-random seeks in file1 as file2 is sequentially built.

I cannot have all of file1 in memory, but can have more than the one
record I am currently using in this shuffle.  How can I speed this up?
-- 
Jeff Percival (jwp at larry.sal.wisc.edu)