Browse Prior Art Database

Partial Passes for Balanced Tape Sort

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

Publishing Venue

IBM

Related People

Parkinson, JCG: AUTHOR

Abstract

Suppose that the merge order for a balanced tape sort is M, and the tape number of sequences put out by the internal sort is N. Let p be the greatest integer such that M/P/ < N. Then, by standard methods, the number of merge passes is p+1.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Partial Passes for Balanced Tape Sort

Suppose that the merge order for a balanced tape sort is M, and the tape number of sequences put out by the internal sort is N. Let p be the greatest integer such that M/P/ < N. Then, by standard methods, the number of merge passes is p+1.

It is, however, possible to merge some of the initial sequences, from the bank of tapes on which they had been placed by the internal sort to the other bank and back again. The normal merge order, blocking factor, etc., are used. If the number of sequences thus passed to and fro was N-M/P/+[N-M/P/ over M/2/-1], then the number of sequences outstanding after this initial double-partial pass would be just M/P/. On completion of the sort, the average number of merge passes would be p+2-[M/P+2/-N over M/2/-1]. This is less than p+1 if N < 2M/P+2/ over 1+M/2/.

A final partial pass is also possible for balanced tape. When the end of the intermediate merge is approached, and there are less than 2M sequences outstanding, just sufficient sequences are taken from the output tapes and merged together, so that there will be exactly M sequences left with which to enter the final merge. The average number of passes is about p+1 - M/P/-1 over N[M/P+1/-N over M/P-1/(M-1) - x over 2], where x is 1 unless this would make the quantity within the floor brackets negative, in which case it is zero. x can be made to be always zero by proceeding in the following manner. Suppose the remainder on dividing the number of sequences entering a pass by M, is g. Then at some stage, normally at the end of the pass, there will be a low-order merge operation with only g input strings. If p is odd, the low-order operation should be taken first in the first pass of the intermediate merge, and last otherwise. Thereafter, it would be taken alternately first and last until the last pass of the intermediate merge, when it is replaced by...