Browse Prior Art Database

Predictor for Radix Exchange Sort

IP.com Disclosure Number: IPCOM000081266D
Original Publication Date: 1974-Apr-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 21K

Publishing Venue

IBM

Related People

Loewner, PG: AUTHOR

Abstract

In the publication of P. Hildebrandt and H. Isbitz, "Radix Exchange-An Internal Sorting Method for Digital Computers," JACM, 1959, pp. 156-163, there is described a radix exchange sort. In this described sort, there is included a partitioning scan, and an ordering of the scans. Each of the scans consists of the examining of a bit position in the key, and the scan partitions the list into two sublists, the first sublist being the one whose bit position that was examined is "0", and the second list being the one whose corresponding bit position is "1". In this connection, it is to be noted that one of the two lists could be empty.

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

Predictor for Radix Exchange Sort

In the publication of P. Hildebrandt and H. Isbitz, "Radix Exchange-An Internal Sorting Method for Digital Computers," JACM, 1959, pp. 156-163, there is described a radix exchange sort. In this described sort, there is included a partitioning scan, and an ordering of the scans. Each of the scans consists of the examining of a bit position in the key, and the scan partitions the list into two sublists, the first sublist being the one whose bit position that was examined is "0", and the second list being the one whose corresponding bit position is "1". In this connection, it is to be noted that one of the two lists could be empty.

Subsequently, the same steps are reapplied to each one of the sublists independently of the other, but, at this time, the bit position that is examined is the next less significant one. Thus, the sequence of bit-position examinations is, conceptually, from the most significant to the least significant. Eventually, when all of the bit positions have been examined, or when the sublists consist of single elements, the list is in sorted order.

This radix exchange sort requires no extra storage except for some bookkeeping locations and operates quite rapidly, provided that all of the scans produce nonempty sublists. The global ordering of the partitioning is similar to that known as "quicksort," which is described in the publication of C.A.R. Hoare, "Quicksort," Computer Journal, April 1962, pp. 10-15, the main difference being as to how an individual partition is obtained. In this latter connection, if N is taken to be the number of elements in the list and B the number of bits to be examined in the key, then the number of operations is of the order N log(2)N, provided that each scan produces two equal length segments. However, the order never exceeds NB. The maximum number of bookkeeping locations which are required is log(2)N, provided that, for subsequent partitioning, there is first chosen the shorter segment of the two lists.

There is described herein a predictor for a radix exchange sort as referred to hereinabove. In this predictor, M represents the binary mask covering the key. A 1 in a bit position in mask M specifies that the corresponding bit position in all keys is included in the sort. A 0 in a bit position in mask M specifies that it is to be omitted from the sort.

If E(i) is taken to represent the key of the current i-th element, the...