Radix sorting method and means for minimizing movement of elements having common prefixes

Claim 1

A computer implemented method for the most significant digit (MSB) radix sorting of a set of keys, each key being associated with a corresponding record, each sort recursion including a distribution phase and a collection phase, comprising the steps of: (a) ascertaining, prior to the distribution phase, whether a typical key can be found which shares a prefix with at least a predetermined number of other keys; (b) in the absence of ascertaining a typical key per step (a), executing a recursire MSB radix sort over the set of keys until singletons are reached; (c) responsive to the detection of a typical key, forming a code word for each key sharing the same prefix as the typical key, said code word comprising an index of the MSB at which the key differs from the typical key and the value of that digit in the key; and (d) responsive to step (c), executing a recursive MSB sort over the set of keys until singletons are reached including forming partitions of predefined sequences of keys wherein each partition contains one or more keys having a distinct code word relative to a selected one of the set of keys, and during each distribution phase, utilizing the code words to avoid the comparison match processing otherwise associated with the shared prefix, thereby speeding up the recursive MSB sort.