Proposed resolution:

This wording is relative to N5001.

1. Modify [alg.merge] as indicated:

   template<class BidirectionalIterator>
     constexpr void inplace_merge(BidirectionalIterator first,
                                  BidirectionalIterator middle,
                                  BidirectionalIterator last);
   template<class ExecutionPolicy, class BidirectionalIterator>
     void inplace_merge(ExecutionPolicy&& exec,
                        BidirectionalIterator first,
                        BidirectionalIterator middle,
                        BidirectionalIterator last);
   template<class BidirectionalIterator, class Compare>
     constexpr void inplace_merge(BidirectionalIterator first,
                                  BidirectionalIterator middle,
                                  BidirectionalIterator last, Compare comp);
   template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
     void inplace_merge(ExecutionPolicy&& exec,
                        BidirectionalIterator first,
                        BidirectionalIterator middle,
                        BidirectionalIterator last, Compare comp);
   template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
            class Proj = identity>
     requires sortable<I, Comp, Proj>
     constexpr I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
   

   -7- […]

   -8- Preconditions: […]

   -9- Effects: Merges two sorted consecutive ranges `[first, middle)` and `[middle, last)`, putting the result of the merge into the range `[first, last)`. The resulting range is sorted with respect to `comp` and `proj`.

   -10- Returns: `last` for the overload in namespace `ranges`.

   -11- Complexity: Let N = last - first:

   1. (11.1) — For the overloads with no `ExecutionPolicy`, and if enough additional memory is available, exactlyat most N - 1 comparisons.

   2. (11.2) — Otherwise, 𝒪(N log N) comparisons.

   In either case, twice as many projections as comparisons.

[ 2025-01-25; Daniel comments ]

The SGI STL archive correctly says "at most" as well.

For N5001, section [alg.merge] p5, it says for `merge()` Complexity (emphasis mine):

For the overloads with no `ExecutionPolicy`, at most N - 1 comparisons and applications of each projection

For N5001, section [alg.merge] p11, it says from `inplace_merge()` Complexity (emphasis mine):

Complexity: Let N = last - first:

1. (11.1) — For the overloads with no `ExecutionPolicy`, and if enough additional memory is available, exactly N - 1 comparisons.

2. (11.2) — Otherwise, 𝒪(N log N) comparisons.

This wording should be (emphasis mine)

Complexity: Let N = last - first:

1. (11.1) — For the overloads with no `ExecutionPolicy`, and if enough additional memory is available, at most N - 1 comparisons.

2. (11.2) — Otherwise, 𝒪(N log N) comparisons.

Consider the 2 sequences in a `std::vector` of `int`s and assume that `inplace_merge` has enough memory:

{ 1 }, { 2, 3, 4, 5, 6, 7 )

N is `7`, 7 elements. So N - 1 is `6`

If you `inplace_merge()` the two sequences, the `1` is compared with `2` and `1` is output. But now the 1st sequence is over, so the 2nd sequence is copied. Only 1 comparison is done, not 6.