Proposed resolution:

This wording is relative to N4659.

1. Edit [alg.merge] as indicated:

   template<class BidirectionalIterator>
   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>
   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);
   

   […]

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

   1. (8.1) — For the overloads with no ExecutionPolicy, if enough additional memory is available, exactly N - 1 comparisons on average, 𝒪(N) comparisons in the worst case.

   2. (8.2) — For the overloads with no ExecutionPolicy if no additional memory is available, 𝒪(N log N) comparisons.

   3. (8.3) — For the overloads with an ExecutionPolicy, 𝒪(N log N) comparisons.

   -9- Remarks: Stable ([algorithm.stable]).

[ 2017-07 Toronto Monday issue prioritization ]

Status to LEWG

At the moment, inplace_merge requires exactly N - 1 comparisons, if enough additional memory is available (and in practice enough additional memory is always available). However, this prohibits implementing the merge operation using forms of binary search, as in Timsort's 'Galloping Mode', a useful optimization for non-uniform input data. It's not really useful to prohibit standard libraries from trying a few extra speculative compares like this, given that users must be prepared for the fallback "not enough memory" 𝒪(N lg N) algorithm.