Browse Prior Art Database

High Capacity Oscillating Sort

IP.com Disclosure Number: IPCOM000077022D
Original Publication Date: 1972-May-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Parkinson, JCG: AUTHOR

Abstract

This sorting technique is an improvement of the oscillating technique as currently implemented under the IBM 360 Operation System. With this new technique in a system using T work tapes, input is cut off after each 1/T of a reel, and a sequence of that length is formed. After T-1 such sequences have been formed, they are merged onto one tape, which still has space for a sequence of length 1/T of a reel. The full-merge order can be preserved throughout the whole process and a file of up to T-1 reels can be sorted.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 1

High Capacity Oscillating Sort

This sorting technique is an improvement of the oscillating technique as currently implemented under the IBM 360 Operation System. With this new technique in a system using T work tapes, input is cut off after each 1/T of a reel, and a sequence of that length is formed. After T-1 such sequences have been formed, they are merged onto one tape, which still has space for a sequence of length 1/T of a reel. The full-merge order can be preserved throughout the whole process and a file of up to T-1 reels can be sorted.

This technique requires that sequences containing predefined amounts of data must be placed on predetermined tapes. If such a quantity of data is converted by the internal sort into an unexpected number of sequences, it may be placed on an unexpected tape by the oscillating algorithm, and if so, a copy may be needed. For instance, it may be planned to place the first sequences of length 1/T reels on tapes number 1, 2, 3 ... If the algorithm places them on tapes number T, 1, 2 ..., nothing has been lost. If, e.g., the sequences come out on tapes 1, 2, 2, 4, ..., then come copying will be required. If the full capacity of the method is needed, the final merge order will be T. Hence, the blocking of the sequences of length (T-1)/T reels written by the intermediate merge, may have to be reduced, which in turn would reduce tape capacity somewhat.

Average performance of the method, as also in straight oscillating, can be improved...