NIST

oscillating merge sort

(algorithm)

Definition: Given n tape drives, one input and n-1 work drives, distribute a portion of the input to n-2 tapes, then merge them onto the final tape reading the n-2 backward. Repeat until n-2 (backward) merged runs have been created, at which time they are merged. Continue building up powers of n-2 batches until done.

Generalization (I am a kind of ...)
external sort.

See also merge sort.

Author: PEB

Implementation

(Pascal)

More information

Sheldon Sobel, Oscillating Sort-A New Sort Merging Technique, Journal of the ACM, 9(3):372-374, July 1962.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 12 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "oscillating merge sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/oscillatingMergeSort.html