Radix Exchange—An Internal Sorting Method for Digital Computers

ABSTRACT

This note describes a new technique—Radix Exchange—for sorting data internal to the high speed memory of an electronic binary digital computer. The technique is faster than Inserting by the ratio (log2n)/n for sorting n = 2c items with values distributed evenly in the range 0 to 2c — 1. Its speed compares favorably with internal merging and it has the significant advantage of requiring essentially no working area in addition to that storage for the data being sorted and the instructions comprising the Radix Exchange routine itself. The nomenclature used is, in most cases, that of E. H. Friend [1].

REFERENCES

• 1: Edward H. Friend, Sorting on Electronic Computer Systems, Journal of the ACM (JACM), v.3 n.3, p.134-168, July 1956 [doi>10.1145/320831.320833]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Design, Measurement, Performance, Theory