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;
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:
1: 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?