Ответ 1
Посмотрите ссылки на std:: merge и std:: inplace_merge вы видите следующие сложности:
Для std::merge:
Не более std:: distance (first1, last1) + std:: distance (first2, last2) - 1 сравнение.
И для std::inplace_merge:
Точно сравнение N-1, если доступно достаточно дополнительной памяти, в противном случае N · log (N), где N = std:: distance (first, last).
if enough additional memory is available имеет очень специфическое значение из примечаний на этой странице:
Эта функция пытается выделить временный буфер, как правило, путем вызова станд:: get_temporary_buffer. Если распределение не выполняется, менее эффективный выбран алгоритм.
std::get_temporary_buffer распределяет память динамически (это важно знать, хотите ли вы использовать std::inplace_merge в узком цикле или иметь ограниченные требования к памяти).
Наконец, ссылки на страницы не упоминаются ( edit: cppreference обновлено в соответствии с комментарием ниже), но в std::merge я не думаю, что d_first может перекрываться либо [first1, last1) или [first2, last2). Это означает, что std::merge должен выводиться в другой диапазон, чем любой из входных диапазонов.
Это также означает следующий вызов (для некоторого RandomAccessContainer a):
std::inplace_merge(a.begin(), a.begin() + n, a.end());
не эквивалентен:
std::merge(a.begin(), a.begin() + n,
a.begin() + n, a.end(), a.begin());
потому что вы не можете выводить в a, если вы читаете его. Вам понадобится:
decltype(a) b;
std::merge(a.begin(), a.begin() + n,
a.begin() + n, a.end(),
std::back_inserter(b));
например.
Интересно, что эта ссылка утверждает, что диапазоны не должны перекрываться (чуть выше раздела возвращаемого значения), которые кажутся более строгими, чем необходимо, потому что это означает что оба входных диапазона также не должны перекрываться. Кроме того, в разделе "Распределение данных" достаточно четко указано, что два входных диапазона доступны только для доступа, поэтому этот слегка искусственный пример:
std::merge(a.begin(), a.end(), a.begin(), a.end(), b.begin());
был бы незаконным в соответствии с этим, но я не уверен. Ни одна из этих ссылок не является стандартом, и, к сожалению, у меня нет ее копии для ссылки на меня, но, возможно, кто-то с доступом может проверить эти требования.
ИЗМЕНИТЬ:
С полезным указателем от TemplateRex до черновика стандарта я могу теперь сказать
N3797 25.4.4 [alg.merge]
2 Требуется: [...] Результирующий диапазон не должен перекрываться ни с одним из исходные диапазоны.
Это точно подтверждает то, что я говорил.