Многие алгоритмы работают с помощью алгоритма слияния чтобы объединить два разных отсортированных массива в один отсортированный массив. Например, заданные в качестве входных данных массивы
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) во всех случаях, но должна выполняться более быстро, учитывая больший объем вспомогательного пространства для использования.
Кто-нибудь знаком с таким алгоритмом (или знаете, где искать его описание?)
