31

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:

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?
9
  • 1
    If anybody can write up an answer from one of my linked resources, I'll take it out of the question; they're only really there to show research effort. (I'm interested to know whether the Honeywell Sorting Capabilities Report has anything, if anyone's got a copy of that!)
    – wizzwizz4
    Commented Aug 12, 2022 at 14:31
  • 3
    Raffzahn - I can't comment on a deleted post - but please finish your post! Good stuff in there! (Alternatively - take some of your good stuff about the 3 different sorts and so on and just jam it into my answer - that's why you're allowed to edit it, as you know!)
    – davidbak
    Commented Aug 12, 2022 at 22:29
  • 3
    @davidbak: You can of course specifically ask/invite someone (in comments) to edit one of your answers; it's ok to collaborate this way. But yes, many people are against significant uninvited additions. (Some are even against corrections by subject-matter expers of mis-statements about facts or code, rather than opinions, thinking that 3rd-party edits should only be for cosmetic changes like formatting or typos.) Commented Aug 13, 2022 at 11:54
  • 2
    Anyway, I'm one of the most in favour of aggressive editing of other people's (and my own) answers, but dumping parts of a deleted answer in yours just for somewhere to put them would definitely require invitation / permission. Commented Aug 13, 2022 at 11:55
  • 1
    @davidbak: Also, SO posts are Creative Commons licensed, so you can copy yourself (with attribution) any parts you want from Raffzahn's deleted answer. Either into a quote block or below a --- hrule with some intro text. (Having Raffzahn edit text into your answer would remove the need for attribution to avoid plagiarism, but as long as you avoid that, you don't strictly need to limit yourself to "fair use" amounts of quoting due to the CC license.) It seems the rep threshold for seeing deleted answers is quite low on this site, since I can at only 2k. Commented Aug 14, 2022 at 6:32

2 Answers 2

32

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 Programming1 (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:

enter image description here enter image description here

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:

enter image description here 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.


1 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"2 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!

2 Update 2022-10-24: TAOCP v4B is in print!

9
  • 2
    "can probably be considered state-of-the-art for the heyday of tape storage" - true and still is.
    – Raffzahn
    Commented Aug 12, 2022 at 22:28
  • 23
    That diagram looks like a musical score. :)
    – Barmar
    Commented Aug 13, 2022 at 14:52
  • 2
    I would love to see a video of a tape drive running this algorithm... Do you know if one happens to exist?
    – Hearth
    Commented Aug 13, 2022 at 15:53
  • 5
    @Hearth - You know ... I am 👉👈 this close to making a little project with a RasPi or something simpler - 10 steppers in a line representing 5 drives, with painted thread spools on them, some stepper motor hats, a bit of python, and, of course, a polyphase merge sort algorithm!
    – davidbak
    Commented Aug 13, 2022 at 23:17
  • 1
    I'd note that Knuth was, at various times, a consultant for Burroughs and that Burroughs ALGOL had sorting as a primitive operation. And while I can't speak for other manufacturers' drives and controllers, the Burroughs drives allowed all operations in both forward and reverse direction with the controller reversing the data transfer to/from memory if necessary. Commented Aug 15, 2022 at 15:48
15

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
5
  • Also - seems what's going on is: initially runs are written on the initial tapes so that each tape has alternating forward and backward runs. You're keeping track of the number of runs on each tape of course. When the next phase starts the tape with the most runs skips past its initial runs (in whatever direction the tape is running) so that merging only begins when each tape has the same number of runs to process - and then, those runs are "synchronized" - the next run on each tape are either all forward or all backward. And to get that ... that's why you sometimes ...
    – davidbak
    Commented Aug 16, 2022 at 15:12
  • need to introduce dummy runs ...? Though if that is the case I don't understand why, in the first example, the dummy runs are written first to the first tape ... how could you know then you're going to need them (unless you already know the length of the input tape)? (Or maybe that's what you meant by keeping track of a file's (i.e., tape's) record count?)
    – davidbak
    Commented Aug 16, 2022 at 15:13
  • 1
    @davidbak - I updated my answer, to include a reference and how a directory partition could be emulated on classic tape drives by "allocating" space with gap commands followed by file mark, data, file mark, then rewind and write directory (record count). If the record count is not known in advance, then "blind distribution" is used, which involves some rearranging of records, which is covered in the reference I linked to. Proprietary algorithms may have had better implementations for "blind distribution".
    – rcgldr
    Commented Aug 16, 2022 at 22:42
  • 1
    @davidbak - I missed your earlier comments. I updated my answer to note initial run size is based on memory size. The alternating ascending | descending runs are needed due to writing forwards and reading backwards (similar to a stack). Also no runs are being skipped, for the sequence in the examples, writes are done left to right, reads are done right to left. For a write forwards | rewind | read forwards algorithm, all runs are ascending.
    – rcgldr
    Commented Aug 16, 2022 at 23:27
  • 1
    @davidbak - as for the dummy runs in my examples, dummy runs are added to the end of the left (largest) group, and at the start of the right (smallest) group. This ensures that a minimal merge will be a single run and one or more dummy runs which just "copies" the single run. After the first merge phase, all dummy runs will be eliminated.
    – rcgldr
    Commented Aug 17, 2022 at 0:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .