Return to Answer

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. 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.

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).

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.

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.

Reference link. Includes an algorithm for "blind distribution" (record count not known in advance), which could involve rearranging records to get near ideal distribution.

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.

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.

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.

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. 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.

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.

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, to emulate a second partition 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.

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 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.