Многие алгоритмы работают с использованием алгоритма слияния для объединения двух различных отсортированных массивов в один отсортированный массив. Например, если в качестве входных данных заданы массивы
1 3 4 5 8
и
2 6 7 9
Объединение этих массивов будет представлять собой массив
1 2 3 4 5 6 7 8 9
Традиционно существует два различных подхода к объединению отсортированных массивов (обратите внимание, что объединение связанных списков происходит совершенно иначе). Во-первых, существуют алгоритмы слияния вне места, которые работают путем выделения временного буфера для хранения, а затем хранения результата слияния во временном буфере. Во-вторых, если два массива являются частью одного входного массива, существуют алгоритмы in-place merge, которые используют только O(1) вспомогательного пространства для хранения и перестраивают две смежные последовательности в одну отсортированную последовательность. Оба эти класса алгоритмов работают за время O(n), но алгоритм слияния вне места имеет тенденцию иметь гораздо меньший постоянный коэффициент, потому что у него нет таких жестких требований к памяти.
Мой вопрос заключается в том, существует ли известный алгоритм слияния, который может "интерполировать" между этими двумя подходами. То есть, алгоритм будет использовать где-то между O(1) и O(n) памяти, но чем больше памяти ему доступно, тем быстрее он работает. Например, если бы мы измеряли абсолютное количество чтений/записей массива, выполняемых алгоритмом, он мог бы иметь время работы в виде n g(s) + f(s), где s - объем доступного ему пространства, а g(s) и f(s) - функции, производные от этого объема доступного пространства. Преимущество этой функции в том, что она может попытаться объединить два массива наиболее эффективным способом с учетом ограничений памяти - чем больше памяти доступно в системе, тем больше памяти она будет использовать и (в идеале) тем выше будет ее производительность.
Более формально алгоритм должен работать следующим образом. Получив в качестве входных данных массив A, состоящий из двух смежных отсортированных диапазонов, переставить элементы в массиве так, чтобы они полностью находились в отсортированном порядке. Алгоритму разрешено использовать внешнее пространство, и его производительность должна быть в худшем случае O(n) во всех случаях, но должна выполняться прогрессивно быстрее, если использовать большее количество вспомогательного пространства.
Кто-нибудь знаком с алгоритмом такого рода (или знает, где можно найти его описание?)