Что делает inplace_merge, если диапазоны не отсортированы?

Question

В документации к inplace_merge говорится, что "диапазоны должны быть отсортированы".Но это не говорит о том, что произойдет, если диапазоны не отсортированы.Я пытался использовать его с несортированными диапазонами, и в результате получается несортированный массив, но это может зависеть от компилятора.Что я могу сделать из отсутствия документации по этому делу - означает ли это, что если диапазоны не отсортированы, результатом будет неопределенное поведение ?(например: разрешен ли совместимый со стандартами компилятор для создания ошибки сегментации в случае, если диапазоны не отсортированы?)

Answer 1

inplace_merge требует сортировки входов, что указано в [alg.merge] :

Требуется: [первый, средний) и [средний, последний) должны быть действительными диапазонами , отсортированными по comp и proj.

Строго говоря, предоставление несортированного ввода в inplace_merge - это неопределенное поведение , конец истории.

Но стандарт также требует, чтобы он был стабильным и O (N) сложность .

Что приводит нас к единственно возможной реализации с использованием алгоритма с двумя указателями : проходите оба диапазона одновременно, «объединяя» их вместе, выбирая наименьшие элементы из обоих на каждом шаге.

Таким образом, на практике, скорее всего, он будет выполнен до конца с несортированным результатом.