Patent ID: 8515976

Claim:
A bit string data sort apparatus for sort processing of keys to be sorted, which keys are expressed as bit strings, comprising: a keys-to-be-sorted storage means that stores the keys to be sorted; a difference bit position calculating means that obtains a difference bit position, which is a position of a first differing bit found by a bit string comparison between a key stored in the keys-to-be-sorted storage means, which key is an object of a classification in classification processing that constitutes the sort processing, and a reference key taken from among keys subject to the classification; a key-to-be-classified difference bit position storage means that, for each difference bit position obtained by the difference bit position calculating means, stores identification information for keys with that difference bit position; a difference bit position classifying means that, for each difference bit position obtained by the difference bit position calculating means, by writing the identification information for the keys with that difference bit position into the key-to-be-classified difference bit position storage means, classifies the keys subject to the classification into groups of keys so that keys in each of the groups have same difference bit position; a sorted key outputting means that outputs a key as a sorted key if there is only one key with the same difference bit position classified by the difference bit position classifying means and, if there is a plurality of keys with the same difference bit position, outputs from among the plurality of keys a key to be the reference key in a next classification processing as the sorted key; and a control means that controls the difference bit position calculating means, the difference bit position classifying means, and the sorted key outputting means so that the difference bit position calculating means obtains the difference bit position by taking all of the keys to be sorted as the object of the classification in an initial processing, and thereafter repeatedly obtains the difference bit position by taking a group of keys consisting of a plurality of keys, which group is classified by the difference bit position classifying means as having the same difference bit position, as the object of a further classification, and the difference bit position classifying means repeatedly classifies the keys subject to the classification into groups of keys so that keys in each of the groups have same difference bit position for each difference bit position obtained by the difference bit position calculating means, and the sorted key outputting means outputs the key as the sorted key when the difference bit position classifying means, for each difference bit position, classifies keys into a group with the same difference bit position.