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.
Initial run size is based on how many records can be sorted in memory. A merge sort could be performed on an array of pointers to records, then the records rearranged according to the sorted pointers (this can be done in O(n) time) and then written to tape as a single run. For an I/O controller that supports descriptor (pointer, count) lists (usually to handle virtual memory blocks randomly scattered in physical memory), the records would not have to be rearranged (the sorted descriptor list would be used). I recall some company getting a patent on this obvious optimization for use with disk based sorts, but not sure when it was granted or if it's expired now.
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 issue is optimizing distribution if the number of records is not known in advance ("blind distribution"), 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, to emulate a second partition as used on modern tape drives. 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.
Modern tape drives have a second "partition" that can be used for metadata (directory) for the data in the primary "partition", such as a record count.
- - -
Reference link. Includes an algorithm for "blind distribution" (record count not known in advance), 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