Polyphase merge sort

From Wikipedia, the free encyclopedia

A polyphase merge sort is an algorithm which decreases the number of runs at every iteration of the main loop by merging runs in pairs. Typically, a merge sort splits items into groups then recursively sorts each group. Once the groups are sorted, they are merged into a final, sorted sequence.

Polyphase merge sorts are ideal for sorting and merging large files. Two pairs of input and output files are opened as file streams. At the end of each iteration, input files are deleted, output files are closed and reopened as input files. The use of file streams makes it possible to sort and merge files which can not be loaded into the computer's main memory.

[edit] See also

• Merge Sort

[edit] References

• Art S. Kagel, polyphase merge sort, in Dictionary of Algorithms and Data Structures (online), Paul E. Black, ed., U.S. National Institute of Standards and Technology. 4 October 2007.[1]

[edit] External links

• Merge sort

v • d • e Sorting algorithms Theory Computational complexity theory | Big O notation | Total order | Lists | Stability | Comparison sort Exchange sorts Bubble sort | Cocktail sort | Odd-even sort | Comb sort | Gnome sort | Quicksort Selection sorts Selection sort | Heapsort | Smoothsort | Strand sort Insertion sorts Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting Merge sorts Merge sort Non-comparison sorts Radix sort | Bucket sort | Counting sort | Pigeonhole sort | Tally sort Others Topological sorting | Sorting network | Bitonic sorter Ineffective/jokeful sorts Bogosort