Content deleted Content added
Renamed 'Variants' to 'In-place merge sort' and added mention of sqrt(n) rotate merge sort |
ping-pong merges |
||
Line 10:
|average-time=<math>\Theta(n\log n)</math>
|space=<math>O(n)</math> total with <math>O(n)</math> auxiliary, <math>O(1)</math> auxiliary with linked lists<ref>{{Harvtxt|Skiena|2008|p=122}}</ref>
}}
Line 233 ⟶ 232:
[[Tournament sort|Tournament replacement selection sorts]] are used to gather the initial runs for external sorting algorithms.
== Ping-pong merge sort ==
Instead of merging two blocks at a time, a ping-pong merge merges four blocks at a time. The four sorted blocks are merged simultaneously to auxiliary space into two sorted blocks, then the two sorted blocks are merged back to main memory. Doing so omits the copy operation and reduces the total number of moves by half. An early public ___domain implementation of a four-at-once merge was by WikiSort in 2014, the method was later that year described as an optimization for [[patience sorting]] and named a ping-pong merge.<ref name="wikisort">{{cite web
|title = WikiSort. Fast and stable sort algorithm that uses O(1) memory. Public ___domain.
|url = https://github.com/BonzaiThePenguin/WikiSort
|last = |date=14 Apr 2014
}}</ref><ref>{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014 |url=http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf}}</ref> Quadsort implemented the method in 2020 and named it a quad merge.<ref name="quadsort">{{cite web
|title = Quadsort is a branchless stable adaptive merge sort.
|url = https://github.com/scandum/quadsort
|last = |date=8 Jun 2022
}}</ref>
== In-place merge sort==
Line 247 ⟶ 257:
|url = https://koreascience.kr/article/CFKO200311922203087.page
|last = |date=1 Sep 2003
}}</ref> This method is employed by the C++ STL library and quadsort.<ref name="quadsort">{{cite web
|title = Quadsort is a branchless stable adaptive merge sort.
|url = https://github.com/scandum/quadsort
| |||