We propose an algebraic framework for the design and implementation of a large class of data-sorting procedures, including all index-digit permutations used in FFTs. We discuss both old and new algorithms in terms of this framework. We show that the algebraic formulation of the new algorithms can be easily encoded using a functional programming language, and that the resulting code introduces no inefficiencies. We present performance results for implementations of three new algorithms for mixed-radix digit-reversal on a Cray C-90 and on a Sun Sparc 5.

A. L. Rosenberg [4] has shown that fully extendible array storage schemes cannot preserve proximity of array positions in any global sense but only in a local sense. The purpose of this note is to consider two problems suggested in [4]. Our first result shows that, for any k array positions of an extendible array, there is a storage scheme which stores array elements that are “close to” the given k positions optimally “close” to each other. The “local diameter of preservation” of a storage scheme is essentially the cardinality of the smallest set of contiguous locations assigned to array positions in a “neighborhood” of a given array position. Our second result shows the nonexistence of “almost everywhere” polynomial bounds of a certain type for local diameters of preservation.