<p>I hope I understood correctly how the ping-pong merge worked. If so here is why it uses two arrays:</p>

<ul>
<li><p>A typical merge operations takes two runs in an array and merges them in another arra; then, it copies the results back into the original array. When you have more than 2 runs to merge, you merge them pairwise into an array, then copy everything back to the original array, and repeat until there are no runs left.</p></li>
<li><p>The ping-pong merge merges runs pairwise into an array, then instead of just copying them back in the original array, it merges the resulting runs pairwise from the temporary array into another array, then to the first temporary array, then to the second one, etc... The goal is to avoid copying everything back to the original array after each series of pairwise merges.</p></li>
</ul>

<p>Now, I guess that your question is actually "why does the ping-pong merge operate back and forth between two temporary arrays instead of merging runs pairwise in a single temporary array, then back to the original array, then back to the temporary array, etc...?"</p>

<p>Honestly, I only have one tentative explanation, and it's not really satisfying: I tend to implement algorithms in C++, and if I wrote the <code>ping_pong_merge</code> algorithm, it could take any pair of random-access iterators, which means that it could handle <code>std::deque</code> (a list of fixed-size arrays) as well as regular arrays. While <code>std::deque</code> has $O(1)$ element access, it is actually slower than <code>std::vector</code> in practice, so using two temporary arrays would ensure that the ping-pong merge only occurs between collections whose random-access is the fastest. This could be a memory vs. performance kind of problem.</p>

CC BY-SA 3.0
2016-05-02T14:09:44.963Z
2016-05-02T19:42:31.590Z
2016-05-02T19:42:31.590Z
Morwenn
<p>A <a href="http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf" rel="nofollow">recent paper</a> out of Microsoft Research describes a new, faster implementation of the patience sort algorithm.  A key part of the implementation is an improved merging strategy dubbed the "ping-pong" merge.  I am confused as to why this merge strategy uses two arrays to perform the merging, instead of just using a single array and always performing a "blind merge" as described in the paper.  It seems that always performing blind merges, and thus only using a single array to perform the merge, would cut down memory usage with no change in runtime.</p>

CC BY-SA 3.0
2014-06-27T13:02:34.533Z
By the way: did I misunderstand the authors, or do they motivate the creation of a synthetic (almost sorted) data set by the existence of "plethora" of real (almost sorted) data instances?
J.y B.y
<ds.algorithms><ds.data-structures><sorting>
Patience Sort+ ping pong merge implementation
dcb
# Patience Sort+ ping pong merge implementation

(Asked by: username_0 on 2014-06-06)

A [recent paper](http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf) out of Microsoft Research describes a new, faster implementation of the patience sort algorithm. A key part of the implementation is an improved merging strategy dubbed the "ping-pong" merge. I am confused as to why this merge strategy uses two arrays to perform the merging, instead of just using a single array and always performing a "blind merge" as described in the paper. It seems that always performing blind merges, and thus only using a single array to perform the merge, would cut down memory usage with no change in runtime.

**Tags:** ds.algorithms, ds.data-structures, sorting
> **Comments:**
> **username_1**: By the way: did I misunderstand the authors, or do they motivate the creation of a synthetic (almost sorted) data set by the existence of "plethora" of real (almost sorted) data instances?  

---

## 1 answers

### Answer by username_2 on 2016-05-02. Score: 2

I hope I understood correctly how the ping-pong merge worked. If so here is why it uses two arrays:

* A typical merge operations takes two runs in an array and merges them in another arra; then, it copies the results back into the original array. When you have more than 2 runs to merge, you merge them pairwise into an array, then copy everything back to the original array, and repeat until there are no runs left.
* The ping-pong merge merges runs pairwise into an array, then instead of just copying them back in the original array, it merges the resulting runs pairwise from the temporary array into another array, then to the first temporary array, then to the second one, etc... The goal is to avoid copying everything back to the original array after each series of pairwise merges.

Now, I guess that your question is actually "why does the ping-pong merge operate back and forth between two temporary arrays instead of merging runs pairwise in a single temporary array, then back to the original array, then back to the temporary array, etc...?"

Honestly, I only have one tentative explanation, and it's not really satisfying: I tend to implement algorithms in C++, and if I wrote the `ping_pong_merge` algorithm, it could take any pair of random-access iterators, which means that it could handle `std::deque` (a list of fixed-size arrays) as well as regular arrays. While `std::deque` has $O(1)$ element access, it is actually slower than `std::vector` in practice, so using two temporary arrays would ensure that the ping-pong merge only occurs between collections whose random-access is the fastest. This could be a memory vs. performance kind of problem.


---

