Browse Prior Art Database

Overlapped Rewind and Merging in Tape Crisscross

IP.com Disclosure Number: IPCOM000077154D
Original Publication Date: 1972-Jun-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

The crisscross technique, with merge order M, proceeds by building up 2M-1 strings of the currently greatest length. It then merges M of these strings, builds up M-1 more, merges M, etc., until M strings of the next length have been produced. The procedure is then repeated with the strings of this new length now defining the currently greatest length. An exception in the current implementation is the string length produced by the internal sort. Strings of this length are merged M at a time as soon as they are produced.

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

Page 1 of 1

Overlapped Rewind and Merging in Tape Crisscross

The crisscross technique, with merge order M, proceeds by building up 2M-1 strings of the currently greatest length. It then merges M of these strings, builds up M-1 more, merges M, etc., until M strings of the next length have been produced. The procedure is then repeated with the strings of this new length now defining the currently greatest length. An exception in the current implementation is the string length produced by the internal sort. Strings of this length are merged M at a time as soon as they are produced.

The crisscross technique can be applied also to strings produced by the internal sort, thus eliminating the necessity of such an exception Taking for example M to be 4, the procedure will be according to the above chart. This chart also illustrates another point, applicable to the use of the crisscross technique with tapes. When building up a set of M-1 strings, one should arrange to place these on work units which already have strings of the next length before placing any on other units. For instance at step 12 above, units 4 and 5 have strings of length 4 and new strings of length 1, while units 1 and 2 have only one older string of length 1 on each.

This is done to decrease the probability of having two strings of the same length on a particular work unit, when an end-of-file condition is encountered. The final merge operation will, in general, have strings of different lengths as input. If the wo...