To achieve a high-speed merge sorting method using a coupled node tree.

The minimum or maximum key is extracted from a plurality of sorted key storage regions containing a key formed by a sorted bit string. A coupled node tree for merging is generated by adding a processing source identifier to identify the sorted key storage region as an extraction source. A write-out of a key into the merged key storage region by the minimum value or the maximum value search of the coupled node tree, deletion processing of the key from the merged key storage region, and an extraction of the key from the sorted key storage region are repeatedly executed for insert processing. Then, a merge sorting is achieved.