The fastest tape sorts were proprietary variations of polyphase merge sort that could take advantage of tape drives that could read backwards for 3 to 7 tape drives (for 8 or more tape drives, standard merge sort is faster). Since these were proprietary, the details have probably been lost.
Reading tape backwards reverses the order, so the distribution and merges operate on ascending and descending runs such that the end result is an ascending sorted file.
Another issue is if the input is from tape, after distribution, that tape has to be rewound and replaced with a working tape, unless there were enough tape drives that the input tape drive could be left idle and the remaining tape drives used to do the sort. For safety, the input tape drive would be write protected (it's write ring removed).
I wrote a 3 stack polyphase merge sort which is similar to what would have been used for tape drives that can read backwards. One complication is tracking run boundaries, but in the case of tape drives, the data block size would be fixed or at least some minimal size, allowing a small block (as opposed to a file mark which takes up space on a tape) to be used as an end of run indicator.
Another detail is an ideal initial distribution if the number of records is not known in advance, but if sorting was to be done on a regular basis, then some method of keeping track of a file's record count would be useful.
- - -
Classic tape drives did not have an end of data marker or care about blank tape, and a trick could be used to store the number of records at the start of a tape, or something similar to a directory. A gap command generated 3 inches of blank tape. When writing a "file" to tape, several gap commands are used to "allocate" space for later, followed by a file mark and then the actual data, then another file mark, then rewinding the tape and writing a single record with the record count, then rewinding and unloading the tape. To read the tape, a single read was done to get the record count, followed by a "space forward file mark" to get to the data.
- - -
Reference link. Includes algorithms for "blind distribution", which could involve rearranging records to get near ideal distribution. I'm not sure how stability was maintained (keeping track of the original order of runs to preserve the original order for equal records).
http://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf
- - -
Example for 13 runs on 3 tapes. Runs are shown in written order, left to right, so they're read right to left. Each run has a suffix of `a` for ascending or `d` for descending:
1d 1a 1d 1a 1d 1a 1d 1a 1a 1d 1a 1d 1a 0
1d 1a 1d 0 2d 2a 2d 2a 2d
0 3a 3d 3a 2d 2a
5d 5a 3a 0
5d 0 8d
0 13a 0
If not an ideal number of runs, dummy runs (0a or 0d) can be used. Example for 9 runs on 3 tapes:
1d 1a 1d 1a 1d 1a 0d 0a 0a 0d 1a 1d 1a 0
1d 1a 1d 0 1d 1a 2d 1a 1d
0 2a 2d 3a 1d 1a
4d 3a 2a 0
4d 0 5d
0 9a 0
Example for 17 runs on 4 tapes
1a 1d 1a 1d 1a 1d 1a 1d 1a 1d 1a 1d 1a 1d 1a 1d 1a 0
1a 1d 1a 1d 1a 0 3d 3a 3d 3a
1a 0 5d 5a 3d 3a
0 9d 5d 3d
17a 0 0 0
Example for 10 runs on 4 tapes:
1a 1d 1a 0d 0a 0d 0a 1d 1a 1d 1a 1d 1a 0d 0a 0d 1a 0
1a 1d 1a 1d 1a 0 2d 1a 1d 1a
1a 0 3d 3a 2d 1a
0 5d 3d 2d
10a 0 0 0