We investigate the problem of stable in-place merging from a ratio k = n/m based point of view where m, n are the sizes of the input sequences with m ≤ n . We introduce a novel algorithm for this problem that is asymptotically optimal regarding the number of assignments as well as comparisons. Our algorithm uses knowledge about the ratio of the input sizes to gain optimality and does not stay in the tradition of Mannila and Ukkonen's work [8] in contrast to all other stable in-place merging algorithms proposed so far. It has a simple modular structure and does not demand the additional extraction of a movement imitation buffer as needed by its competitors. For its core components we give concrete implementations in form of Pseudo Code. Using benchmarking we prove that our algorithm performs almost always better than its direct competitor proposed in [6]. As additional sub-result we show that stable in-place merging is a quite simple problem for every ratio k ≥ m~(1/2) by proving that there exists a primitive algorithm that is asymptotically optimal for such ratios.
展开▼
机译：我们从比率k = n / m的角度研究稳定就地合并的问题，其中m，n是m≤n的输入序列的大小。我们针对此问题引入了一种新颖的算法，该算法在分配数量和比较方面都渐近最优。与迄今为止提出的所有其他稳定的就地合并算法相比，我们的算法使用有关输入大小比率的知识来获得最优，并且不遵循Mannila和Ukkonen的工作[8]的传统。它具有简单的模块化结构，不需要竞争对手提供额外的运动仿制缓冲器。对于其核心组件，我们以伪代码的形式给出具体的实现。使用基准测试，我们证明了我们的算法几乎总是比[6]中提出的直接竞争对手表现更好。作为额外的子结果，我们通过证明存在一种对于这种比率渐近最优的原始算法，证明了对于每个比率k≥m〜（1/2）而言，稳定的就地合并都是一个非常简单的问题。
展开▼
