METHOD, DEVICE AND PROGRAM FOR KEY REDUCTION UPON SORTING

摘要

PROBLEM TO BE SOLVED: To reduce data amounts of reading out and writing out which occur in every radix sort.

SOLUTION: A method comprises the steps of: storing an input integer sequence of a sorting target in a partial sorting sequence storage means; taking upper K bits of the input integer sequence of the sorting target to create a histogram of appearance frequency of a bit position of the upper K bits specified by sorting processing means; storing the created histogram in histogram storage means; repeating M/K times (provided that M: an integer, K: a unit for performing a radix sort) processing to store a partially sorted sequence in which the upper K bits are sorted based on the histogram read out from the histogram storage means in the partial sorting sequence storage means; and creating a sorted integer sequence.

COPYRIGHT: (C)2013,JPO&INPIT