Most efficient inplace merge algorithms (stable and unstable)

Question

I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and m, and the goal is to merge it in place into a single sorted array (of size n + m).

I have found this reference (Geffet et al., 2000), but I was wondering if better algorithms were found since then.

I am interested in research in three categories about these algorithms:

• stable inplace merge (regardless of the "implementation difficulty" of the algorithm)
• unstable inplace merge (regardless of the "implementation difficulty" of the algorithm)
• "easily implementable" stable inplace merge

What are the current bests algorithms in these categories?

Answer 1

TLDR

• The latest stable one with linear moves is from 2008 and with detailed description can be found here. According to their benchmarks, it is less than two times slower than standard merge that uses external memory. But it should be noted, that all benchmarks about merging assume fast comparison functions.

Stable in-place merging

The following four are optimal regarding the complexity of comparisons and moves. But none of them reaches the lower bound for comparisons or moves. The last two have pseudo-code given and here in more detail. But still important smaller parts are missing, making it not easy to reproduce the codes.

• "Asymptotically efficient in-place merging" by V. Geffert, J. Katajainen, T. Pasanen (2000)

  The algorithm requires at most $m_1(t + 1) + m_2/2^t + o(m1)$ comparisons ($t = \lfloor\log_2(m_2/m_1)\rfloor)$ and $5m_2 + 12m_1 + o(m_1)$ moves, where $m_1$ and $m_2$ are the sizes of two ordered sublists to be merged, and $m_1\leq m_2$.

  The algorithm is probably difficult to implement, a pseudo-code is missing.

• "Optimizing stable in-place merging" by Jingchao Chen (2002)

  The optimized algorithm is simpler than their algorithm, and makes at most $m_1(t + 1) + m_2/2^t + o(m_1 + m_2)$ comparisons and $6m_2 + 7m_1 + o(m_1 + m_2)$ moves.

  The algorithm is probably difficult to implement, a pseudo-code is missing.

• "On Optimal and Efficient in Place Merging", Kim & Kutzner (2006)

• "Ratio based stable in-place merging", Kim & Kutzner (2008)

Unstable in-place merging

• I don't have enough information about this category. But at least the Kim & Kutzner 2006 algorithm is based on an unstable algorithm. Also Chen's method is available which is shown below more detailed.

Easy implementable

... and stable

All of the following algorithms are asymptotically optimal regarding the number of comparisons. In practice, they often require more comparisons than algorithms that are linear in the number of comparisons. All of the following algorithms are non-linear in the number of moves ($\approx (m+n)\cdot \log_2(m+n)$). The last two algorithms have a worst-case when the size ratio of $m$ and $n$ is to huge that leads to a stackoverflow because of memory usage. The papers show how to prevent it using hybrid calling into Recmerge or Symmerge if some criteria requires this. All of these methods require few comparisons in best case and don't move data in the best case.

• Recmerge: In my tests, surprisingly low number of comparisons even for $m=n$. It seems to converge against $1.10\cdot(m+n)$ comparisons in worst-case. The performance is very near to Symmerge, assuming the same optimizations (left side one element, right side one element) and same rotation algorithm.

• Symmerge: in my tests, always higher number of comparisons and moves than equally-optimized Recmerge, most of the time $\approx 2\%$ faster than Recmerge, though.

• Splitmerge: in my tests, always worse performance than Symmerge and Recmerge and higher number of comparisons and moves than the others.

• Duelmerge: in my tests, faster than the others, but more moves and more comparisons. The performance improvements come from cache-efficiency and maybe also vectorization of the block swapping. The algorithm given in the paper has bugs in the binary search where the three 1s appear. Also a check for terminating the recursion is missing, but is given in the paper of the following method. A working code can be found in the source code of this collection.

• UnfairDuelMerge: contains an update to the DuelMerge pseudo-code. The given pseudo-code for the new method (at least for me) was not enough to try this. In theory, it is very similar to DuelMerge, but uses floating-hole exchange instead of block-swapping for doing less moves. In practice, in optimized compiled languages the runtime performance is the same. It would be interesting to see, if the floating-hole exchange requires less energy, though.

• The merging routine used in GlideSort: The complexity seems to be $(m+n)\cdot \log_2(m+n)$ to merge two adjacent input sequences of length $m$ and $n$. In practice, this will be two times faster than the other methods with the same complexity. Though, it is currently unclear how many comparisons and moves it requires. The number of comparisons is probably higher than $m+n-1$ in worst case.

... and not stable

• Chen's method: converges against $3\cdot (m+n)$ moves and $1.26\cdot (m+n)$ comparisons in the worst-case where $m=n$. An optimizations exists, that brings it down to $1.13\cdot (m+n)$ comparisons and the same number of moves as before. The algorithm is cache-inefficient and thus sometimes a little bit slower than Duelmerge, which is rather cache-efficient. The default pseudo-code given requires signed integers, not unsigned, otherwise some inputs will fail. My tests show, that the method also requires the number of moves, if the data is already sorted. But this can be easily worked around by just adding in front: while $right.last\geq left.last$: $right$ -= $1$. Once this is not fullfilled anymore: start with the normal algorithm. With this last optimization, the algorithm will be stable in best case and don't moves data in best case.

Comparison strategies

• Most algorithms that use binary searching perform extremely well, when the size difference of $m$ and $n$ is huge or if many duplicates are in the data.
• In other words: when $m=n$ and no duplicates: this the worst-case for many algorithms. But there exist also the block-based algorithms that try to extract distinct keys to allow losing the order without losing stability (the first four). In those cases many distinct keys are good, but it also means that the algorithms adapt less good to already partly sorted data and have a worse best-case than Recmerge and Symmerge.
• A linear search makes it possible to guarantee a worst case of $m+n-1$ comparisons if and only if elements from $M$ are only compared with elements from $N$ and each element is compared at most one time. Some algorithms compare elements from $M$ with elements from $M$ although they originally were already in order, which obviously prevents us from reaching the lower bound. This can be done to achieve a lower number of moves with the cost of a higher number of comparisons.
• Algorithms that uses linear searching can in general also use binary searching. The other way around is not always possible or at least can bring the algorithm in a higher complexity class.

Worst-case optimal number of comparisons

• The standard algorithm requires only $m+n-1$ comparisons in worst-case, which is worst-case optimal, but requires extra memory of up to $m$.
• Probably none of the publicly known in-place merging methods can merge with the worst-case optimal number of comparisons and is better than quadratic in the number of moves