<h1>TLDR</h1>
<ul>
<li>The latest stable one with linear moves is from 2008 and with detailed description can be found <a href="http://itbe.hanyang.ac.kr/ak/papers/performant-in-place-merging.pdf" rel="nofollow noreferrer">here</a>. 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.</li>
</ul>
<h1>Stable in-place merging</h1>
<p>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 <a href="http://itbe.hanyang.ac.kr/ak/papers/performant-in-place-merging.pdf" rel="nofollow noreferrer">here</a> in more detail. But still important smaller parts are missing, making it not easy to reproduce the codes.</p>
<ul>
<li><p>&quot;Asymptotically efficient in-place merging&quot; by V. Geffert, J. Katajainen, T. Pasanen (2000)</p>
<blockquote>
<p>The algorithm requires at most
<span class="math-container">$m_1(t + 1) + m_2/2^t + o(m1)$</span> comparisons (<span class="math-container">$t = \lfloor\log_2(m_2/m_1)\rfloor)$</span> and <span class="math-container">$5m_2 + 12m_1 + o(m_1)$</span> moves,
where <span class="math-container">$m_1$</span> and <span class="math-container">$m_2$</span> are the sizes of two ordered sublists to be merged, and <span class="math-container">$m_1\leq m_2$</span>.</p>
</blockquote>
<p>The algorithm is probably difficult to implement, a pseudo-code is missing.</p>
</li>
<li><p>&quot;Optimizing stable in-place merging&quot; by Jingchao Chen (2002)</p>
<blockquote>
<p>The optimized algorithm is simpler than their algorithm, and makes at most <span class="math-container">$m_1(t + 1) + m_2/2^t + o(m_1 + m_2)$</span> comparisons and <span class="math-container">$6m_2 + 7m_1 + o(m_1 + m_2)$</span> moves.</p>
</blockquote>
<p>The algorithm is probably difficult to implement, a pseudo-code is missing.</p>
</li>
<li><p>&quot;<a href="http://itbe.hanyang.ac.kr/ak/papers/sofsem2006.pdf" rel="nofollow noreferrer">On Optimal and Efficient in Place Merging</a>&quot;, Kim &amp; Kutzner (2006)</p>
</li>
<li><p>&quot;<a href="http://itbe.hanyang.ac.kr/ak/papers/tamc2008.pdf" rel="nofollow noreferrer">Ratio based stable in-place merging</a>&quot;, Kim &amp; Kutzner (2008)</p>
</li>
</ul>
<h1>Unstable in-place merging</h1>
<ul>
<li>I don't have enough information about this category. But at least the Kim &amp; Kutzner 2006 algorithm is based on an unstable algorithm. Also Chen's method is available which is shown below more detailed.</li>
</ul>
<h1>Easy implementable</h1>
<h2>... and stable</h2>
<p>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 (<span class="math-container">$\approx (m+n)\cdot \log_2(m+n)$</span>). The last two algorithms have a worst-case when the size ratio of <span class="math-container">$m$</span> and <span class="math-container">$n$</span> 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 <em>and</em> don't move data in the best case.</p>
<ul>
<li><p>Recmerge: In my tests, surprisingly low number of comparisons even for <span class="math-container">$m=n$</span>. It seems to converge against <span class="math-container">$1.10\cdot(m+n)$</span> 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.</p>
</li>
<li><p><a href="http://itbe.hanyang.ac.kr/ak/papers/esa2004.pdf" rel="nofollow noreferrer">Symmerge</a>: in my tests, always higher number of comparisons and moves than equally-optimized Recmerge, most of the time <span class="math-container">$\approx 2\%$</span> faster than Recmerge, though.</p>
</li>
<li><p><a href="http://itbe.hanyang.ac.kr/ak/papers/sofsem2007.pdf" rel="nofollow noreferrer">Splitmerge</a>: in my tests, always worse performance than Symmerge and Recmerge and higher number of comparisons and moves than the others.</p>
</li>
<li><p><a href="https://academic.oup.com/comjnl/article-abstract/60/9/1271/3062794" rel="nofollow noreferrer">Duelmerge</a>: 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 <code>1</code>s 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 <a href="http://sortierkino.bplaced.net/Sortierkino.zip" rel="nofollow noreferrer">this</a> collection.</p>
</li>
<li><p><a href="https://academic.oup.com/comjnl/article-abstract/63/5/701/5381951?redirectedFrom=fulltext" rel="nofollow noreferrer">UnfairDuelMerge</a>: 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.</p>
</li>
<li><p>The merging routine used in <a href="https://github.com/orlp/glidesort" rel="nofollow noreferrer">GlideSort</a>: The complexity seems to be <span class="math-container">$(m+n)\cdot \log_2(m+n)$</span> to merge two adjacent input sequences of length <span class="math-container">$m$</span> and <span class="math-container">$n$</span>. 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 <span class="math-container">$m+n-1$</span> in worst case.</p>
</li>
</ul>
<h2>... and not stable</h2>
<ul>
<li><a href="https://www.sciencedirect.com/science/article/abs/pii/S002001900500339X" rel="nofollow noreferrer">Chen's method</a>: converges against <span class="math-container">$3\cdot (m+n)$</span> moves and <span class="math-container">$1.26\cdot (m+n)$</span> comparisons in the worst-case where <span class="math-container">$m=n$</span>. An optimizations <a href="https://github.com/tstj/chens-merging-algorithm" rel="nofollow noreferrer">exists</a>, that brings it down to <span class="math-container">$1.13\cdot (m+n)$</span> 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 <span class="math-container">$right.last\geq left.last$</span>: <span class="math-container">$right$</span> -= <span class="math-container">$1$</span>. 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.</li>
</ul>
<h1>Comparison strategies</h1>
<ul>
<li>Most algorithms that use binary searching perform extremely well, when the size difference of <span class="math-container">$m$</span> and <span class="math-container">$n$</span> is huge <em>or</em> if many duplicates are in the data.</li>
<li>In other words: when <span class="math-container">$m=n$</span> 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.</li>
<li>A linear search makes it possible to guarantee a worst case of <span class="math-container">$m+n-1$</span> comparisons if and only if elements from <span class="math-container">$M$</span> are only compared with elements from <span class="math-container">$N$</span> and each element is compared at most one time. Some algorithms compare elements from <span class="math-container">$M$</span> with elements from <span class="math-container">$M$</span> 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.</li>
<li>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.</li>
</ul>
<h1>Worst-case optimal number of comparisons</h1>
<ul>
<li>The standard algorithm requires only <span class="math-container">$m+n-1$</span> comparisons in worst-case, which is worst-case optimal, but requires extra memory of up to <span class="math-container">$m$</span>.</li>
<li>Probably none of the publicly known in-place merging methods can merge with the worst-case optimal number of comparisons <em>and</em> is better than quadratic in the number of moves</li>
</ul>

CC BY-SA 4.0
2023-01-30T20:32:40.037Z
2023-04-20T14:08:57.310Z
2023-04-20T14:08:57.310Z
Guest
<p>I am currently researching the best algorithms available to achieve an <strong>inplace merge</strong> operation: consider two consecutive sorted arrays of size <code>n</code> and <code>m</code>, and the goal is to merge it in place into a single sorted array (of size <code>n + m</code>).</p>

<p>I have found <a href="http://www.sciencedirect.com/science/article/pii/S0304397598001625">this reference</a> (Geffet et al., 2000), but I was wondering if better algorithms were found since then.</p>

<p>I am interested in research in three categories about these algorithms:</p>

<ul>
<li>stable inplace merge (regardless of the "implementation difficulty" of the algorithm)</li>
<li>unstable inplace merge (regardless of the "implementation difficulty" of the algorithm)</li>
<li>"easily implementable" stable inplace merge</li>
</ul>

<p>What are the current bests algorithms in these categories?</p>

CC BY-SA 3.0
2016-02-29T23:52:34.603Z
Does cache efficiency matter? It does in practice.
Chad Brewbaker
<ds.algorithms><sorting><implementation><analysis-of-algorithms><bibliography>
Most efficient inplace merge algorithms (stable and unstable)
Vincent
# Most efficient inplace merge algorithms (stable and unstable)

(Asked by: username_0 on 2016-02-26)

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](http://www.sciencedirect.com/science/article/pii/S0304397598001625) (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?

**Tags:** ds.algorithms, sorting, implementation, analysis-of-algorithms, bibliography

> **Comments:**
> **username_1**: Does cache efficiency matter? It does in practice.  

---

## 1 answers

### Answer by username_2 on 2023-01-30. Score: 6 | Accepted answer

# TLDR

* The latest stable one with linear moves is from 2008 and with detailed description can be found [here](http://itbe.hanyang.ac.kr/ak/papers/performant-in-place-merging.pdf). 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](http://itbe.hanyang.ac.kr/ak/papers/performant-in-place-merging.pdf) 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](http://itbe.hanyang.ac.kr/ak/papers/sofsem2006.pdf)", Kim & Kutzner (2006)
* "[Ratio based stable in-place merging](http://itbe.hanyang.ac.kr/ak/papers/tamc2008.pdf)", 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](http://itbe.hanyang.ac.kr/ak/papers/esa2004.pdf): 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](http://itbe.hanyang.ac.kr/ak/papers/sofsem2007.pdf): in my tests, always worse performance than Symmerge and Recmerge and higher number of comparisons and moves than the others.
* [Duelmerge](https://academic.oup.com/comjnl/article-abstract/60/9/1271/3062794): 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 `1`s 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](http://sortierkino.bplaced.net/Sortierkino.zip) collection.
* [UnfairDuelMerge](https://academic.oup.com/comjnl/article-abstract/63/5/701/5381951?redirectedFrom=fulltext): 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](https://github.com/orlp/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](https://www.sciencedirect.com/science/article/abs/pii/S002001900500339X): converges against $3\cdot (m+n)$ moves and $1.26\cdot (m+n)$ comparisons in the worst-case where $m=n$. An optimizations [exists](https://github.com/tstj/chens-merging-algorithm), 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


---

