A comparison between the polyphase and oscillating sort techniques

ABSTRACT

Read-backward Polyphase sorting provides more efficient use of the tapes available to a sort than most other sorting techniques. Backward Polyphase produces a continuous merging process from n - 1 tapes where n is the total number of tapes being used in the sorting process. Any of the available presorting techniques may be used in conjunction with the Polyphase merge sort provided that the presort has the capability of producing both ascending and descending strings and distributing the strings on the various tapes as required by the Polyphase Merge.

REFERENCES

• 1: GILSTAD, R .L . Polyphase merge sorting--an advanced technique. Proc. Eastern Joint Comput. Conf. 1960, 143-48.
• 2: R. L. Gilstad, Read-backward polyphase sorting, Communications of the ACM, v.6 n.5, p.220-223, May 1963 [doi>10.1145/366552.366562]
• 3: RADIO CORPORATION OF AMERICA, ASTRO ELECTRONICS DI- VISION AND APPLIED DATA RESEARCH, INC. Design specifications for Acsi-matic sort/merge system. Report No. SR-61-3, June 1961.
• 4: Sheldon Sobel, Oscillating Sort—A New Sort Merging Technique, Journal of the ACM (JACM), v.9 n.3, p.372-374, July 1962 [doi>10.1145/321127.321133]
• 5: Armando G. Mendoza, A dispersion pass algorithm for the polyphase merge, Communications of the ACM, v.5 n.10, p.502-504, Oct. 1962 [doi>10.1145/368959.368970]
• 6: GASSNER, BETTY JANE. Proof of a conjecture concerning sorting by replacement-selection. Unpublished paper, 1958.
• 7: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962