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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 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? $\endgroup$– J..y B..yJun 27, 2014 at 13:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
