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)，但是如果使用更大量的辅助空间，则应该更快速地运行。

有人熟悉这种算法(或者知道在哪里寻找一个描述？)