Polyphase merge sort
A polyphase merge sort is a variation of a bottom-up merge sort that sorts a list using an initial uneven distribution of sub-lists (runs), primarily used for external sorting, and is more efficient than an ordinary merge sort when there…
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A polyphase merge sort is a variation of a bottom-up merge sort that sorts a list using an initial uneven distribution of sub-lists (runs), primarily used for external sorting, and is more efficient than an ordinary merge sort when there are fewer than eight external working files (such as a tape drive or a file on a hard drive). A polyphase merge sort is not a stable sort.
Balanced merge sort
A merge sort splits the records of a dataset into sorted runs of records and then repeatedly merges sorted runs into larger sorted runs until only one run, the sorted dataset, remains. A ‘balanced’ merge sort using four working files organizes them as a pair of input files and a pair of output files.
The dataset is distributed evenly between two of the working files, either as sorted runs or in the simplest case, single records, which can be considered to be sorted runs of size 1. Once all of the dataset is transferred to the two working files, those two working files become the input files for the first merge iteration.
Each merge iteration merges runs from the two input working files, alternating the merged output between the two output files, again distributing the merged runs evenly between the two output files (until the final merge iteration). Once all of the runs from the two inputs files are merged and output, then the output files become the input files and vice versa for the next merge iteration.
The number of runs decreases by a factor of 2 at each iteration, such as 64, 32, 16, 8, 4, 2, 1. For the final merge iteration, the two input files only have one sorted run (1/2 of the dataset) each, and the merged result is a single sorted run (the sorted dataset) on one of the output files. This is also described at .
If there are only three working files, then a balanced merge sort merges sorted runs from two working files onto a single working file, then distributes the runs evenly between the two output files. The merge iteration reduces run count by a factor of 2, the redistribute iteration doesn't reduce run count (the factor is 1).
Each iteration could be considered to reduce the run count by an average factor of ≈ 1.41. If there are 5 working files, then the pattern alternates between a 3 way merge and a 2 way merge, for an average factor of ≈ 2.45.
In general, for an even number N of working files, each iteration of a balanced merge sort reduces run count by a factor of N/2, while for an odd number N of working files, each iteration reduces the run count by an average factor of = /2.
Polyphase merge
For N ... | * (consumed) File 3 (in ): | * | * (consumed) ... possible runs that have already been read | marks the read pointer of the file marks end of file Stepping back to the previous iteration, we were reading from 1 and 2. One run is merged from 1 and 2 before file 1 goes empty. Notice that file 2 is not completely consumed—it has one run left to match the final merge (above).
File 1 (in ): ... | * ... | * File 2 (in ): | * --> | * File 3 (out): * Stepping back another iteration, 2 runs are merged from 1 and 3 before file 3 goes empty. File 1 (in ): | ... | * File 2 (out): --> * File 3 (in ): ... | * | * Stepping back another iteration, 3 runs are merged from 2 and 3 before file 2 goes empty.
File 1 (out): * File 2 (in ): ... | * --> ... | * File 3 (in ): | * | * Stepping back another iteration, 5 runs are merged from 1 and 2 before file 1 goes empty. File 1 (in ): ... | * ... | * File 2 (in ): | * --> | * File 3 (out): *
Distribution for polyphase merge sort
Looking at the perfect 3 file case, the number of runs for merged working backwards: 1, 1, 2, 3, 5, ... reveals a Fibonacci sequence. The sequence for more than 3 files is a bit more complicated; for 4 files, starting at the final state and working backwards, the run count pattern is {1,0,0,0}, {0,1,1,1}, {1,0,2,2}, {3,2,0,4}, {7,6,4,0}, {0,13,11,7}, {13,0,24,20}, ... .
For everything to work out optimally, the last merge phase should have exactly one run on each input file. If any input file has more than one run, then another phase would be required. Consequently, the polyphase merge sort needs to be clever about the initial distribution of the input data's runs to the initial output files.
For example, an input file with 13 runs would write 5 runs to file 1 and 8 runs to file 2. In practice, the input file will not have the exact number of runs needed for a perfect distribution. One way to deal with this is by padding the actual distribution with imaginary "dummy runs" to simulate an ideal run distribution.
A dummy run behaves like a run with no records in it. Merging one or more dummy runs with one or more real runs just merges the real runs, and merging one or more dummy runs with no real runs results in a single dummy run. Another approach is to emulate dummy runs as needed during the merge operations.
"Optimal" distribution algorithms require knowing the number of runs in advance. Otherwise, in the more common case where the number of runs is not known in advance, "near optimal" distribution algorithms are used. Some distribution algorithms include rearranging runs.
If the number of runs is known in advance, only a partial distribution is needed before starting the merge phases. For example, consider the 3 file case, starting with n runs in File_1. Define F i = F i−1 + F i−2 as the ith Fibonacci number.
If n = F i , then move F i−2 runs to File_2, leaving F i−1 runs remaining on File_1, a perfect run distribution. If F i i+1 , move n−F i runs to File_2 and F i+1 −n runs to File_3. The first merge iteration merges n−F i runs from File_1 and File_2, appending the n−F i merged runs to the F i+1 −n runs already moved to File_3.
File_1 ends up with F i−2 runs remaining, File_2 is emptied, and File_3 ends up with F i−1 runs, again a perfect run distribution. For 4 or more files, the math is more complicated, but the concept is the same.
Comparison versus balanced merge sort
After the initial distribution, a balanced merge sort using 4 files will sort 16 single record runs in 4 iterations of the entire dataset, moving a total of 64 records in order to sort the dataset after the initial distribution. A polyphase merge sort using 4 files will sort 17 single record runs in 4 iterations, but since each iteration but the last iteration only moves a fraction of the dataset, it only moves a total of 48 records in order to sort the dataset after the initial distribution.
In this case, balanced merge sort factor is 2.0, while polyphase overall factor is ≈2.73. To explain how the reduction factor is related to sort performance, the reduction factor equations are: reduction_factor = exp(number_of_runs*log(number_of_runs)/run_move_count) run_move_count = number_of_runs * log(number_of_runs)/log(reduction_factor) run_move_count = number_of_runs * log_reduction_factor(number_of_runs) Using the run move count equation for the above examples: balanced merge sort → , polyphase merge sort → .
Here is a table of effective reduction factors for polyphase and balanced merge sort listed by number of files, based on actual sorts of a few million records. This table roughly corresponds to the reduction factor per dataset moved tables shown in fig 3 and fig 4 of polyphase merge sort.pdf files | average fraction of data per iteration | | polyphase reduction factor on ideal sized data | | | balanced reduction factor on ideal sized data | | | | 3 .73 1.94 1.41 (sqrt 2) 4 .63 2.68 2.00 5 .58 3.20 2.45 (sqrt 6) 6 .56 3.56 3.00 7 .55 3.80 3.46 (sqrt 12) 8 .54 3.95 4.00 9 .53 4.07 4.47 (sqrt 20) 10 .53 4.15 5.00 11 .53 4.22 5.48 (sqrt 30) 12 .53 4.28 6.00 32 .53 4.87 16.00 In general, polyphase merge sort is better than balanced merge sort when there are fewer than 8 files, while balanced merge sort starts to become better at around 8 or more files.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1283628003 under CC BY-SA 4.0; modifications have been made.