Editing Merge sort (section)

=== Further variants ===
Merge sort was one of the first sorting algorithms where optimal speed up was achieved, with Richard Cole using a clever subsampling algorithm to ensure ''O''(1) merge.<ref>{{Cite journal |last1=Cole |first1=Richard |date=August 1988 |title=Parallel merge sort |journal=SIAM J. Comput. |volume=17 |issue=4 |pages=770–785 |citeseerx=10.1.1.464.7118 |doi=10.1137/0217049|s2cid=2416667 }}</ref> Other sophisticated parallel sorting algorithms can achieve the same or better time bounds with a lower constant. For example, in 1991 David Powers described a parallelized [[quicksort]] (and a related [[radix sort]]) that can operate in ''O''(log ''n'') time on a [[CRCW]] [[parallel random-access machine]] (PRAM) with ''n'' processors by performing partitioning implicitly.<ref>{{cite book |last=Powers |first=David M. W. |chapter-url=http://citeseer.ist.psu.edu/327487.html |chapter=Parallelized Quicksort and Radixsort with Optimal Speedup |title=Proceedings of International Conference on Parallel Computing Technologies, Novosibirsk |date=1991 |archive-url=https://web.archive.org/web/20070525234405/http://citeseer.ist.psu.edu/327487.html |archive-date=2007-05-25}}</ref> Powers further shows that a pipelined version of Batcher's [[Bitonic sorter|Bitonic Mergesort]] at ''O''((log ''n'')<sup>2</sup>) time on a butterfly [[sorting network]] is in practice actually faster than his ''O''(log ''n'') sorts on a PRAM, and he provides detailed discussion of the hidden overheads in comparison, radix and parallel sorting.<ref>{{cite conference |last=Powers |first=David M. W. |url= http://david.wardpowers.info/Research/AI/papers/199501-ACAW-PUPC.pdf |title=Parallel Unification: Practical Complexity |conference=Australasian Computer Architecture Workshop Flinders University |date=January 1995}}</ref>