Можно ли сделать слияние на месте без временного хранения?

Question

Я просто подумал, что если бы я реализовал std::inplace_merge, это бы выглядело примерно так:

template <class Bi, class Cmp>
void inplace_merge(Bi first, Bi middle, Bi last, Cmp cmp) {
    if(first != last) {
        typedef typename iterator_traits<Bi>::value_type T;
        typedef typename iterator_traits<Bi>::difference_type Dist;

        const Dist count = distance(first, last);
        if(count != 1) {
            // can I avoid this allocation?
            T *const temp = new T[count];       
            merge(first, middle, middle, last, temp, cmp);      
            copy(temp, temp + count, first);
            delete [] temp;
        }
    }
}

Я знаю, что я мог бы просто использовать существующую реализацию, но это отчасти важно. Мне было просто любопытно, был ли алгоритм лучше, чем я знаю.

Причина, по которой это пришло в голову, состоит в том, что большая часть стандартной библиотеки c ++ (все STL, если я правильно помню) позволяет пользователю указывать, как и где выполнять распределение, но если std::inplace_merge требует распределения по проекту, это кажется, что нет способа контролировать это, если бы это было проблемой.

Я думаю, что намек на ответ исходит из самого стандарта в отношении сложности std::inplace_merge:

Сложность: когда достаточно дополнительных память доступна, (последняя - первая) - 1 сравнение. Если нет дополнительной памяти доступен алгоритм с сложность N log N (где N равно до последней-первой) может быть использован.

Для меня это означает, что известные эффективные версии алгоритма требуют дополнительной памяти. Я читаю это правильно? Если да, то есть ли упоминание о том, откуда должно появиться хранилище?

Answer 1

Существует несколько известных алгоритмов слияния на месте, хотя некоторые из них довольно сложны.Общий способ, которым они работают, - это слияние с места, используя некоторые элементы массива в качестве внешнего пространства хранения.Я знаю, что в «Элементах программирования» Алекса Степанова и Пола МакДжонса подробно описан один алгоритм.

Я недавно читал статью о слиянии на месте под названием «Практическое слияние на месте» , в которой подробнодовольно простой алгоритм для такого слияния.Я кодировал реализацию этого алгоритма способом, близким к интерфейсу std::inplace_merge, хотя есть несколько отличий.Возможно, там есть что-то, что вам может пригодиться?