许多算法通过使用merge algorithm将两个不同的排序数组合并为单个排序数组来工作 . 例如，作为输入给出数组
1 3 4 5 8
和
2 6 7 9
这些数组的合并将是数组
1 2 3 4 5 6 7 8 9
传统上，似乎有两种不同的方法来合并排序的数组（请注意，合并链表的情况完全不同） . 首先，存在不合适的合并算法，它们通过为存储分配临时缓冲区，然后将合并的结果存储在临时缓冲区中来工作 . 其次，如果两个数组碰巧是同一输入数组的一部分，则in-place merge algorithms只使用O（1）辅助存储空间，并将两个连续序列重新排列成一个排序序列 . 这两类算法都在O（n）时间内运行，但是异地合并算法往往具有低得多的常数因子，因为它没有如此严格的内存要求 .
我的问题是，是否存在可以在这两种方法之间“插入”的已知合并算法 . 也就是说，算法会在O（1）和O（n）内存之间使用，但它可用的内存越多，运行的速度就越快 . 例如，如果我们要测量算法执行的数组读/写的绝对数量，它可能具有ng（s）f（s）形式的运行时间，其中s是可用空间量和g （s）和f（s）是可从该可用空间量导出的函数 . 这个函数的优点是它可以尝试在给定内存约束的情况下以最有效的方式将两个数组合并在一起 - 系统上可用的内存越多，它将使用的内存越多，并且（理想情况下）它将具有更好的性能 . .
更正式地说，该算法应该如下工作 . 给定输入一个由两个相邻的排序范围组成的数组A，重新排列数组中的元素，使元素完全按排序顺序排列 . 允许该算法使用外部空间，并且在所有情况下其性能应该是最坏情况的O（n），但是在给定更大量的辅助空间的情况下应该更快地运行 .
是否有人熟悉这种算法（或知道在哪里查找一个？）
2 回答
至少根据文档，in-place merge function in SGI STL是自适应的和"its run-time complexity depends on how much memory is available" . 源代码可用，你当然至少可以检查这个 .
编辑：STL有
inplace_merge，它将适应可用的临时缓冲区的大小 . 如果临时缓冲区至少与其中一个子阵列一样大，则为O（N） . 否则，它会将合并拆分为两个子合并并进行递归 . 拆分需要O（log N）来找到要旋转的另一个子数组的右侧部分（二进制搜索） .因此，它取决于您可用的内存量，从O（N）到O（N log N） .