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 16 November 2009.
HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:
Paul E. Black, "oscillating merge sort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/oscillatingMergeSort.html