PARALLEL MERGESORTING

摘要

The invention relates to a sorting method (1100) for sorting input data distributed over local memory partitions (401, 402, 403, 404) of a plurality of interconnected processing nodes (701, 702), the sorting method comprising: sorting (1101) the distributed input data locally per processing node (701, 702) by deploying first processes on the processing nodes (701, 702) to produce a plurality of sorted lists on the local memory partitions (401, 402, 403, 404) of the processing nodes (701, 702); creating (1102) a sequence of range blocks (703, 704, 713, 714) on the local memory partitions of the processing nodes (701, 702), wherein each range block is configured to store data values falling within its range; copying (1103) the plurality of sorted lists to the sequence of range blocks (703, 704, 713, 714) by deploying second processes on the processing nodes (701, 702), wherein each range block (703, 704, 713, 714) receives elements of the sorted lists which values are falling within its range; sorting (1104) the elements of the range blocks (703, 704, 713, 714) locally per processing node (701, 702) by using the second processes to produce sorted elements on the range blocks (703, 704, 713, 714); and reading (1105) the sorted elements from the sequence of range blocks (703, 704, 713, 714) sequentially with respect to their range to obtain the sorted input data.