Адаптивный к памяти алгоритм слияния?

Многие алгоритмы работают с использованием алгоритма слияния для объединения двух различных отсортированных массивов в один отсортированный массив. Например, если в качестве входных данных заданы массивы

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

Кто-нибудь знаком с алгоритмом такого рода (или знает, где можно найти его описание?)

22
задан GEOCHET 10 August 2015 в 16:02
поделиться