Parallel sorting apparatus, method, and program

A parallel sorting method for sorting, by parallel processing, input data composed of a plurality of data pieces, comprising:

• calculating a plurality of reference values serving as boundaries of intervals used for allocating the input data depending on a magnitude of a value thereof on the basis of the input data;
• partitioning the input data into a plurality of input data regions;
• calculating, by parallel processing, mapping information used for allocating the data in each of the partitioned input data regions to the plurality of intervals that have boundaries on the calculated reference values, wherein the mapping information is information that is used, when the data contained in the plurality of input data regions are to be allocated to the plurality of intervals, for determining output data regions corresponding to the intervals where the data allocated to the plurality of intervals are to be accumulated;
• allocating, by parallel processing, data in each of the input data regions to the plurality of intervals in accordance with the calculated mapping information;
• and
• individually sorting by parallel processing the allocated data in the plurality of intervals,
• wherein the number of data pieces contained in each of the intervals for each of the input data regions is counted, and the counted results for each input data region are aggregated so that the mapping information is calculated such that each of the plurality of output data regions have a size that allows the data allocated to the intervals to be accumulated without mutual overlapping of the data.

A storage medium for storing a parallel sorting program for causing a computer to perform processing of sorting, by parallel processing, input data composed of a plurality of data pieces and for causing a computer to execute:

• a procedure of calculating a plurality of reference values serving as boundaries of intervals used for allocating the input data depending on a magnitude of a value thereof on the basis of the input data;
• a procedure of partitioning the input data into a plurality of input data regions;
• a procedure of calculating, by parallel processing, mapping information used for allocating the data in each of the partitioned input data regions to the plurality of intervals that have boundaries on the calculated reference values, wherein the mapping information is information that is used, when the data contained in the plurality of input data regions are to be allocated to the plurality of intervals, for determining output data regions corresponding to the intervals where the data allocated to the plurality of intervals are to be accumulated;
• a procedure of allocating, by parallel processing, data in each of the input data regions to the plurality of intervals in accordance with the calculated mapping information;
• and
• a procedure of individually sorting by parallel processing the allocated data in the plurality of intervals,
• wherein the number of data pieces contained in each of the intervals for each of the input data regions is counted, and the counted results for each input data region are aggregated so that the mapping information is calculated such that each of the plurality of output data regions have a size that allows the data allocated to the intervals to be accumulated without mutual overlapping of the data,
• and wherein the storage medium is a non-transitory computer-readable data storage medium on which the parallel sorting program is stored.