Editing Merge sort (section)

== 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        = |website = [[GitHub]]
 |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        = |website = [[GitHub]]
 |date=8 Jun 2022
}}</ref>