内存自适应合并算法？

许多算法通过使用合并算法将两个不同的排序数组合并为单个排序数组.例如,作为输入给出数组

1  3  4  5  8

和

2  6  7  9

这些数组的合并将是数组

1  2  3  4  5  6  7  8  9

传统上,似乎有两种不同的方法来合并排序的数组(请注意,合并链表的情况完全不同).首先,存在不合适的合并算法,它们通过为存储分配临时缓冲区,然后将合并的结果存储在临时缓冲区中来工作.其次,如果两个数组碰巧是同一输入数组的一部分,则存在仅使用O(1)辅助存储空间并将两个连续序列重新排列成一个排序序列的就地合并算法.这两类算法都在O(n)时间内运行,但是异地合并算法往往具有低得多的常数因子,因为它没有如此严格的内存要求.

我的问题是,是否存在可以在这两种方法之间"插入"的已知合并算法.也就是说,算法会在O(1)和O(n)内存之间使用,但它可用的内存越多,运行的速度就越快.例如,如果我们要测量算法执行的数组读/写的绝对数量,它可能具有ng(s)+ f(s)形式的运行时,其中s是可用空间量和g(s)和f(s)是可从该可用空间量导出的函数.这个函数的优点是它可以尝试在给定内存约束的情况下以最有效的方式将两个数组合并在一起 - 系统上可用的内存越多,它将使用的内存越多,并且(理想情况下)它将具有更好的性能. .

更正式地说,该算法应该如下工作.给定输入一个由两个相邻的排序范围组成的数组A,重新排列数组中的元素,使元素完全按排序顺序排列.允许该算法使用外部空间,并且在所有情况下其性能应该是最坏情况的O(n),但是在给定更大量的辅助空间的情况下应该更快地运行.

是否有人熟悉这种算法(或知道在哪里查找一个？)

至少根据文档,SGI STL中的就地合并功能是自适应的,"它的运行时复杂性取决于可用的内存量".源代码可用,你当然至少可以检查这个.