Parallelized in-place radix sorting

A data set sorting apparatus, comprising:

• a multiple processor computing apparatus comprising a first processor and a second processor;
• a memory coupled to the multiple processor computing apparatus;
• a data sorting processor, coupled to the multiple processor computing apparatus and the memory, the data sorting processor configured to:
• divide a data storage into a plurality of buckets comprising at least a first bucket and a second bucket, each bucket being associated with a respective key value, the data storage containing a plurality of data items;
• identify, within each bucket of the plurality of buckets, a respective plurality of stripes;
• define a plurality of data stripe sets, each data stripe set in the plurality of data stripe sets comprising one respective stripe within each respective bucket of the plurality of buckets, the plurality of data stripe sets comprising at least a first data stripe set and a second data stripe set that is separate from the first data stripe set;
• perform a first in-place partial bucket radix sort using an initial radix value on data items contained within the first data stripe set;
• perform a second in-place partial bucket radix sort using the initial radix value on data items contained within the second data stripe set;
• group, after performing the first in-place partial bucket radix sort and the second in-place partial radix sort, incorrectly sorted data items in each bucket into a respective incorrect data item group within each bucket, the incorrectly sorted data items comprising data items within the first bucket but having a respective radix value associated with a different bucket,
• the data sorting processor is configured to group by at least grouping incorrectly sorted data items in the first bucket with a first processor and grouping incorrectly sorted data items in the second bucket with a second processor that is different from the first processor while grouping incorrectly sorted data items in the first bucket with the first processor;
• perform a radix sort using the initial radix on items within the respective incorrect data item group;
• and
• produce a first level sorted output comprising the plurality of data items within the data storage sorted according to the initial radix.

A computer program product for sorting a data set, the computer program product comprising:

• a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
• dividing a data storage into a plurality of buckets comprising at least a first bucket and a second bucket, each bucket being associated with a respective key value, the data storage containing a plurality of data items;
• identifying, within each bucket of the plurality of buckets, a respective plurality of stripes;
• defining a plurality of data stripe sets, each data stripe set in the plurality of data stripe sets comprising one respective stripe within each respective bucket of the plurality of buckets, the plurality of data stripe sets comprising at least a first data stripe set and a second data stripe set that is separate from the first data stripe set;
• performing a first in-place partial bucket radix sort using an initial radix value on data items contained within one data stripe set;
• performing a second in-place partial bucket radix sort using the initial radix value on data items contained within the second data stripe set;
• grouping, after performing the first in-place partial bucket radix sort and the second in-place partial radix sort, incorrectly sorted data items in each bucket into a respective incorrect data item group within each bucket, the incorrectly sorted data items comprising data items within the first bucket but having a respective radix value associated with a different bucket,
• the grouping comprising grouping incorrectly sorted data items in the first bucket with a first processor and grouping incorrectly sorted data items in the second bucket with a second processor that is different from the first processor while grouping incorrectly sorted data items in the first bucket with the first processor;
• performing a radix sort using the initial radix on items within the respective incorrect data item group;
• and
• producing a first level sorted output comprising the plurality of data items within the data storage sorted according to the initial radix.