Browse Prior Art Database

SORT Method Using SORT/MERGE Instructions

IP.com Disclosure Number: IPCOM000087392D
Original Publication Date: 1977-Jan-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Bradley, CT: AUTHOR

Abstract

Known approaches to sorting data include the provision of a special SORT/MERGE utility program or, alternately, require the computer user to write SORT and MERGE routines using existing COMPARE/MOVE/JUMP instructions. General-purpose utility programs occupy large amounts of memory and disk storage because all practical applications of the SORT/MERGE utility must be provided for. On the other hand, computer user written SORT/MERGE routines using general purpose COMPARE/MOVE/JUMP instructions may be tailored to occupy less memory and disk storage, but require significantly more execution time when run on interpretively executing processors, such as the IBM 3601.

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

Page 1 of 3

SORT Method Using SORT/MERGE Instructions

Known approaches to sorting data include the provision of a special SORT/MERGE utility program or, alternately, require the computer user to write SORT and MERGE routines using existing COMPARE/MOVE/JUMP instructions. General-purpose utility programs occupy large amounts of memory and disk storage because all practical applications of the SORT/MERGE utility must be provided for. On the other hand, computer user written SORT/MERGE routines using general purpose COMPARE/MOVE/JUMP instructions may be tailored to occupy less memory and disk storage, but require significantly more execution time when run on interpretively executing processors, such as the IBM 3601.

The SORT and MERGE instructions described herein allow user-tailored SORT programs to be written which require substantially less execution time because less interpretation overhead is involved.

The instructions themselves include an Op code field and a parameter list address field which points to the first byte of the respective parameter list. The SORT parameter list includes flag bytes to indicate ascending or descending key SORT sequence, etc., address bytes to indicate the start address, and the ending address of the SORT data block and the work data block, and length bytes to indicate the length of each data item, the displacement of SORT key field in the data items from the beginning of the data item, and the length of the SORT key field within the data items.

Likewise, the MERGE parameter list includes flag bytes, bit positions of which indicate ascending or descending SORT key sequence, input block one empty, input block two empty, output block full, sequence check, data set swap flag, etc. Also address bytes are included in the MERGE parameter list to indicate the start, ending and current address of the two input blocks and output block, as well as length bytes to indicate the length of each item, the displacement of the SORT key from the beginning of the items and the length of the SORT key. In addition, the MERGE parameter list includes two MERGE unit size bytes which indicate the number of bytes in the smallest string of ordered items that are input from or output to a disk data set while merging.

By way of example, the LSORT and LMERGE instructions may be used to sort the items in a disk data set which is too large to read into random-access memory at one time. This example involves one SORT pass and one or more MERGE passes. Assuming an ascending SORT, five data sets are defined on the disk. They are the original data set A to be sorted, and four work data sets labeled PUT1, PUT2, GET1 and GET2. For example, data set A may comprise a plurality of 256 byte blocks, each holding 10 data items of length 25 bytes. After initializing the SORT and MERGE parameter lists, the SORT pass comprising the following steps is executed:

1) Initialize an output switch indicator to 1 indicating that all writes to the disk go to PUT1.

2)...