Return to Answer

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!}

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!} 

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:

¹ _{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!}

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!}

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 5 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 10 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:

¹ _{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!}

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:

¹ _{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!}