# Patience Sort+ ping pong merge implementation

A recent paper 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.

• 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? Jun 27, 2014 at 13:02

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.