Browse Prior Art Database

Reduction in Number of Passes for Unit Record Merge/Sort

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

Publishing Venue

IBM

Related People

Benjamin, K: AUTHOR [+2]

Abstract

This is a card sorting technique which substantially reduces the number of card passes required for a unit record merge/sort. To do this, the number of strings in the input file is decreased prior to the merge/sort, by making a replacement sort pass.

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

Reduction in Number of Passes for Unit Record Merge/Sort

This is a card sorting technique which substantially reduces the number of card passes required for a unit record merge/sort. To do this, the number of strings in the input file is decreased prior to the merge/sort, by making a replacement sort pass.

The merge/sort is a commonly used method for sorting unit record files on systems equipped with multiple hopper input devices (e.g. the IBM 2560 Multiple Function Card Machine).

A typical prior art arrangement of two-hopper, two-stacker merge/ sorts is shown in Figs. 1A and 1B. To begin a merge/sort (Fig. 1A), the operator divides the file of cards into approximately equal parts and places one part in each hopper. Corresponding strings from the hoppers are merged and the resulting longer strings are selected to alternate stackers, as shown in Fig. 1B. At the end of the pass, each stacker's process is repeated. The file is continuously passed in this manner until only one string remains. At this point the file is sorted.

If the file for Figs. 1A and 1B is divided optimally for the first pass of a two- hopper merge/sort, the total number of passes is P = [log(2)S] where S = number of strings in the input file.

For a file in random order, S is approximately one-half the file size.

This card sorting technique decreases the value of S prior to the merge/sort by making a replacement sort/pass. For its application, the sorting device must be capable of writing as well as reading records.

To begin a pass, as shown in Fig. 2A, an original card deck (input file) is placed in one of two hoppers, and a deck of blank or reusable cards is placed in the other hopper. The successive contents of original cards are then read into available computer memory, until it is full. The lowest (if sorting ascending) record stored is then written out to head the first string, a...