Editing External sorting (section)

== External distribution sort ==
External distribution sort is analogous to [[quicksort]]. The algorithm finds approximately <math>\tfrac{M}{B}</math> pivots and uses them to divide the {{mvar|N}} elements into approximately equally sized subarrays, each of whose elements are all smaller than the next, and then recurse until the sizes of the subarrays are less than the [[blocking (data storage)|block size]]. When the subarrays are less than the block size, sorting can be done quickly because all reads and writes are done in the [[cache (computing)|cache]], and in the [[external memory model]] requires <math>O(1)</math> operations.

However, finding exactly <math>\tfrac{M}{B}</math> pivots would not be fast enough to make the external distribution sort [[asymptotically optimal]]. Instead, we find slightly fewer pivots. To find these pivots, the algorithm splits the {{mvar|N}} input elements into <math>\tfrac{N}{M}</math> chunks, and takes every <math>\sqrt{\tfrac{M}{16B}}</math> elements, and [[recursion|recursively]] uses the [[median of medians]] algorithm to find <math>\sqrt{\tfrac{M}{B}}</math> pivots.<ref name="Aggarwal88">{{cite journal|last1=Aggarwal|first1=Alok|last2=Vitter|first2=Jeffrey|author2-link=Jeffrey Vitter|title=The input/output complexity of sorting and related problems|journal=[[Communications of the ACM]]|volume=31|issue=9|pages=1116–1127|date=1988|doi=10.1145/48529.48535|url=https://hal.inria.fr/inria-00075827/file/RR-0725.pdf}}</ref>

There is a [[Duality (mathematics)|duality]], or fundamental similarity, between merge- and distribution-based algorithms.<ref>[[J. S. Vitter]], ''[http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf Algorithms and Data Structures for External Memory]'', Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008, {{ISBN|978-1-60198-106-6}}.</ref>