What "spectacular to watch" algorithms were used for sorting tapes?

Question

Python's heapq.__about__ variable contains an anecdote (François Pinard, circa 2000):

[1] The disk balancing algorithms which are current, nowadays, are more annoying than clever, and this is a consequence of the seeking capabilities of the disks. On devices which cannot seek, like big tape drives, the story was quite different, and one had to be very clever to ensure (far in advance) that each tape movement will be the most effective possible (that is, will best participate at "progressing" the merge). Some tapes were even able to read backwards, and this was also used to avoid the rewinding time. Believe me, real good tape sorts were quite spectacular to watch! From all times, sorting has always been a Great Art! :-)

I appreciate sorting algorithm visualisations (audibilisations?) like SORTDEMO.BAS and The Sound of Sorting, but these are only really available for random-access sorting algorithms. Those are nice, but I imagine that sequential-access sorting algorithms would have a beauty that these lack. (Music is, after all, about sequential patterns.)

The only trouble is that – apart from cocktail sort and (polyphase) merge sort – I can't find really find any! A web search turns up:

• A Yahoo! Groups thread with some source snippets from OS/360 and a load of technical details I don't understand – but no sorting algorithm;

• An IBM Mainframes thread about speeding up tape sorts, which quotes from the "SORT Manual", which is not this guide to SYNCSORT;

• The Honeywell Series 200 software manual Programming and Operating Procedures for the Programs Tape Sort C and Collate C, which gives a high-level "Summary Description" of its algorithm in Section I (enough to understand it's a variant of polyphase merge sort; not enough to re-implement it), and references a document I can't find:

  ¹: For more detailed information concerning the sorting techniques applied in Tape Sort C, refer to Honeywell Technical Bulletin No. 118 entitled Sorting Capabilities Report, File Number 127.6105.0200.00.00.

• C++ code, presumably written by a student of an unknown CSC317 university course, demonstrating a very inefficient tape sorting algorithm: almost certainly not one used in practice;

• Algorithm for External Sorting, Multiway Merge, Polyphase Merge, Replacement Selection, which explains some of the techniques mentioned in Sort C and Collate C;

• Some academic papers: Subroutinized tape sorting (1967) (that I can't access; thanks, Springer!); and Parallelism in tape-sorting (1974), which describes three algorithms (one "well known and widely used", and two derivative algorithms).

These are of limited usefulness to me. There's a lot of stuff I don't understand, and the only information I can get out of this is high-level, theoretical descriptions of algorithms. There are always optimisations you can make for the hardware you're working with; those implementation details can contribute as much to the character of a sort as the high-level algorithm it's implementing. I want to know what these "real good tape sorts" look like!

What significant algorithms were used to sort data records stored on tapes?

• What algorithms improved on the state of the art?
• What algorithms were useful with particular hardware setups?
• What algorithms were most popular / widely-used during magnetic tape's heyday?

Answer 1

Sorting on tape is actually mostly merging. And the canonical never-to-be-surpassed source of information on that is Knuth's masterwork The Art Of Computer Programming¹ (aka TAOCP). Specifically Volume 3 "Sorting and Searching" Section 5.4 "External Sorting".

(Images below from 2nd edition, 1998).

You can probably find this stuff available as images or otherwise online at various spots, but here, for posterity are custom-taken photos from my copy.

First, a fabulous visualization of tape merging in a 4-page pull out chart - kind of clipped a bit at the right end - followed by the chart legend:

Embed the legend firmly in your consciousness and then trace out the merging patterns on the chart while your imagination pictures 6 5lb reels of tape spinning back and forth and back and forth under the control of ginormous high-torque motors while thin films of magnetic tape bounce up and down and up and down in 12 vacuum columns ... don't forget to stop and change tapes in the right sequence when the console typewriter commands you!

Here, BTW, is the table of contents for section 5.4:

With respect to "What algorithms were most popular / widely-used during magnetic tape's heyday?" - 7-track tape was introduced in 1952 and 9-track in 1964. (See wikipedia.) The first edition of TAOCP volume 3 was published in 1968. So this section can probably be considered state-of-the-art for the heyday of tape storage.

---

¹ _{TAOCP is still being written, and still excellent. He's currently working on Chapter 7 "Combinatorial Algorithms". Volume 4A is in print, volume 4B is in "beta"² via "fascicles" of various subsections, and volumes 4C and 4D haven't gotten that far. Can't wait, though! Volume 4 is really good stuff!}

² _{Update 2022-10-24: TAOCP v4B is in print!}

Answer 2

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.

A polyphase merge sort is not stable, so if stability is required, then a record index needs to be added to each record and included with record comparisons. These indexes are added during distribution and removed in the final merge.

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 (a 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 generates 3 inches of blank tape. When writing a "file" to tape, several gap commands are used to "allocate" space for a "directory" record, followed by a file mark and then the actual data, then another file mark, rewinding the tape, writing a "directory" record that includes a record count, rewinding and unloading the tape. To read the tape, a single read is done to get the record count, followed by a "space forward file mark" to get to the data. I did this myself back in the 1970's, but I don't know how common an emulated directory partition was in the early days of tape sorts.

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.

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