Patent ID: 8332410
Filing Date: 2012-12-11
Classification: G06F

Abstract:
1. A bit string merge sort method that sorts into ascending order or descending order all the keys consisting of bit strings stored in a plurality of sorted key storage areas, wherein in each sorted key storage area all the keys are sorted in ascending order or descending order, comprising: a merge tree generating step that generates a coupled node tree that holds a key in the plurality of sorted key storage areas as an index key by extracting the key that is a minimum value or maximum value from each of the plurality of sorted key storage areas and inserting the key into the coupled node tree which is used in a bit string search and comprises a root node and a node pair, the node pair being a branch node and a leaf node, or a pair of branch nodes, or a pair of leaf nodes located in adjacent storage areas, wherein the root node is a node that expresses a starting point of the tree and, which is a leaf node when there is one node in the tree and a branch node when there are two or more nodes in the tree, the branch node includes a discrimination bit position of a search key with which a bit string search is performed and position information indicating a position of a primary node, which is one node of a node pair of a link target, and the leaf node includes an index key that is a bit string that is the target of a search, and wherein the leaf node includes a processing source identifier that identifies the sorted key storage area wherefrom the key has been extracted; a merge step that performs a minimum or maximum value search on the coupled node tree and obtains either a smallest key that is the minimum value or a largest key that is the maximum value as a search result along with its processing source identifier and stores the smallest key or the largest key in a merged key storage area; a key deleting step that deletes the smallest key or largest key from the coupled node tree; a next key extracting step that extracts a next key, which is a next minimum value for the smallest key or a next maximum value for the largest key, from the sorted key storage area pointed to by the processing source identifier that has been obtained in the merge step; a next key inserting step that inserts the extracted next key into the coupled node tree; and wherein the merge step, the deleting step, the next key extracting step, and the next key inserting step are repeated until all the keys are extracted from the plurality of sorted key storage areas and are stored in the merged key storage area.