Browse Prior Art Database

Repeated Selection Sort Permitting L/2 Parallel Comparisons

IP.com Disclosure Number: IPCOM000095114D
Original Publication Date: 1965-Sep-01
Included in the Prior Art Database: 2005-Mar-07
Document File: 3 page(s) / 58K

Publishing Venue

IBM

Related People

Iverson, KE: AUTHOR

Abstract

The drawings show a sorting system which permits a repeated selection sort with replacement permitting L/2 parallel comparisons. L is the number of levels in the sorting tree. The number of levels in the tree must be even. In a 4-level tree, two simultaneous comparisons can be made. In a 6-level tree, three simultaneous comparisons can be made, etc.

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

Repeated Selection Sort Permitting L/2 Parallel Comparisons

The drawings show a sorting system which permits a repeated selection sort with replacement permitting L/2 parallel comparisons. L is the number of levels in the sorting tree. The number of levels in the tree must be even. In a 4-level tree, two simultaneous comparisons can be made. In a 6-level tree, three simultaneous comparisons can be made, etc.

Assume thirty-one T registers whose contents are organized as in drawing A. Field Z indicates whether or not the data addressed by the contents of the corresponding address field is legitimate, i. e., a 1 = legitimate, a 0 = not legitimate. Field S specifies sign change of the item, if S = 0, used to provide both +00 and -00 dummy items. Address field A is the address in memory, relative to a base address, of information to be sorted.

When the registers are organized and connected as in drawing B, sorting can occur simultaneously in levels 1 and 3 or 2 and 4. To start, positions 1... 15 are set to -00. Z = 0 and S = 0.

Positions 16... 31 are loaded with the memory addresses of the information to be sorted. Z = 1 and S = 1. Positions 2 and 3 constitute the single pair in level 1. Positions 4 and 5 are one of two pairs in level 2. Positions 8 and 9 are one of four pairs in level 3. Positions 16 and 17 are one of eight pairs in level 4.

During each odd phase, positions 2 and 3 are compared as are also two positions forming a pair in level 3. During each even phase, two positions forming a pair in level 2 are compared as are also two positions forming a pair in level 4. To start, pair 2-3 and pair 8-9 are compared simultaneously. Since positions 1... 15 contain in effect -00, an equal is the result of each compare. When an equal occurs, the lower numbered register is moved to the left one level in the tree, i. e., T2 is removed to T1 and T8 is moved to T4. Since each row of T is moved as a unit, the Z and S values associated with 2 and 8 are also moved to 1 and 4. This creates a vacancy in positions 2 and 8. The subsequent even phase compare is at positions 4-5 in level 2 and positions 16-17 in level 4. Since positions 4-5 are equal, that is, -00, position 4 i...