Polyphase merge sort

Polyphase merge sort

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.

ee also

* Merge Sort

References

* Art S. Kagel, "polyphase merge sort", in [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures] (online), Paul E. Black, ed., U.S. National Institute of Standards and Technology. 4 October 2007. [http://www.nist.gov/dads/HTML/polyphmrgsrt.html]

External links

* [http://www.egr.unlv.edu/~larmore/Courses/CSC269/S00/Assignments/mergesort.html Merge sort]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Cycle sort — Example of cycle sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance Θ(n2) …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”