<p>A method of operating a computer to sort a set of keys each associated with a corresponding record comprises partitioning the keys into subsets and sorting each subset of keys in a predefined sequence, wherein said partitioning is into subsets each containing keys having a distinct codeword relative to a selected one of the set of keys. In an embodiment the selected key is selected by randomly sampling the keys to determine a typical key and selecting that key. If a typical key cannot be identified a conventional MSB sorting method is used. The method is applied recursively to fully sort a set of keys. <IMAGE></p>