Sorting an array consisting of a large number of elements

An apparatus for merge-sorting an array consisting of a large number of elements by utilizing a multiway merging process which generates one output sequence from a plurality of input sequences, the apparatus comprising:

• a storage unit configured to store the array consisting of a large number of elements;
• and
• a sorted-array generation unit configured to:
• (i) produce an input sequence by pairing, for each element, a key for use in a comparison during sorting with an index identifying the element, where one element in the array consisting of a large number of elements or one sorted array of elements makes an input sequence for the multiway merging process, (ii) execute the multiway merging process on a plurality of input sequences without rearranging the elements based on which input sequences have been produced, and (iii) rearrange the elements stored in the storage unit in accordance with output sequences generated so as to generate a sorted array of elements which will make an input sequence for the multiway merging process at a following stage,
• wherein, after an initial stage of processing, processing by the sorted-array generation unit is iteratively executed using all of the large number of elements as the base of input sequences for the multiway merging process, processing at each stage following the initial stage is performed by executing processing that repeats the processing by the sorted-array generation unit using all sorted arrays that were generated by the multiway merging process in the preceding stage as the base of new input sequences for the multiway merging process, which generates a sorted array in which all of the large number of elements are sequentially sorted.

A computer-implemented method, the method comprising:

• executing the multiway merging process on N input sequences without rearranging the elements based on a plurality of input sequences;
• and
• rearranging the elements, based on which the input sequences have been produced, according to an output sequence that has been generated by the multiway merging process in the executing step so as to generate a sorted array of elements;
• and
• determining a number of bits of the key so that a combination of the key and the index has a first number of bits until the number of elements contained in input sequences for the multiway merging process reaches a predetermined threshold, and when the number of elements exceeds the predetermined threshold, determining the number of bits of the key so that the combination has a second number of bits which is greater than the first number of bits.

A computer program product, the computer program product comprising:

• one or more computer readable hardware storage devices and program instructions stored on the one or more computer readable hardware storage devices, the program instructions comprising:
• program instructions to execute the multiway merging process on N input sequences without rearranging the elements based on a plurality of sequences;
• and
• program instructions to rearrange the elements, based on which the input sequences have been produced, according to an output sequence that has been generated by the multiway merging process in the executing step so as to generate a sorted array of elements;
• and
• program instructions to determine a number of bits of the key so that a combination of the key and the index has a first number of bits until the number of elements contained in input sequences for the multiway merging process reaches a predetermined threshold, and when the number of elements exceeds the predetermined threshold, program instructions to determine the number of bits of the key so that the combination has a second number of bits which is greater than the first number of bits.