Partitioning of sorted lists for multiprocessors sort and merge

A computer implemented method of sorting a list of N elements using P processors, where P is an integer greater than 2, and wherein the processors, each having access to storage containing the list, cooperate in parallel to provide the sorted list, the computer implemented method comprising the steps of:

• a) accessing the list from said storage;
• b) dividing the accessed list into P sub-lists of approximately N/P elements, the sub-lists residing in said storage;
• c) each processor accessing and sorting one of the sub-lists, the sorted sub-lists residing in said storage,
• d) each processor accessing the sorted sub-lists upon completion of the sorting step;
• e) defining P-1 partition boundaries, each of the partition boundaries being defined by one of P-1 of the processors, said partition boundaries dividing the lists into nearly equal partitions of elements having values less than all of the elements of a succeeding partition;
• and
• f) each of the processors merging one of the partitions.

Apparatus for partitioning multiple presorted lists of elements comprising:

• a plurality of processors each having access to storage containing the presorted lists, each processor comprising:
• means for accessing said storage to obtain said presorted lists;
• means for selectively and iteratively adding elements from said presorted lists to a partitioning list, said means for selectively and iteratively adding being coupled with said means for accessing;
• means for selecting an initial partition boundary for said partitioning list, said means for selecting being coupled with said means for accessing;
• means for determining a size modifier based on the desired number of elements above the partition boundary versus the actual number of elements above the partition boundary, said means for determining a size modifier being coupled with said means for accessing;
• means for determining a magnitude modifier based on the number of elements below the partition boundary which are less than the magnitude of the largest element above the partition boundary, said means for determining a magnitude modifier being coupled with said means for accessing;
• and
• means for modifying the partition boundary as a function of said size modifier and said magnitude modifier following each iterative addition of elements, said means for modifying being coupled with said means for accessing.

Apparatus for partitioning multiple presorted lists of elements comprising:

• a plurality of processors each having access to storage containing the presorted lists, each processor comprising:
• means for accessing said storage to obtain said presorted lists;
• means for selectively and iteratively adding elements from said presorted lists to a partitioning list, said means for selectively and iteratively adding being coupled with said means for accessing;
• means for selecting an initial partition boundary for the partitioning list, said means for selecting being coupled with said means for accessing;
• means for determining a size modifier, said means for determining a size modifier being coupled with said means for accessing;
• means for determining a magnitude modifier, said means for determining a magnitude modifier being coupled with said means for accessing;
• and
• means for modifying the partition boundary as a function of the size modifier and magnitude modifier following each iterative addition of elements, said means for modifying being coupled with said means for accessing.