4196. Complexity of inplace_merge() is incorrect

Section: 26.8.6 [alg.merge] Status: Voting Submitter: Stephen Howe Opened: 2025-01-22 Last modified: 2025-02-07

Priority: 4

View other active issues in [alg.merge].

View all other issues in [alg.merge].

View all issues with Voting status.

Discussion:

For N5001, section 26.8.6 [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 26.8.6 [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 ints 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.

[2025-01-25; Daniel comments]

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

[2025-02-07; Reflector poll]

Set status to Tentatively Ready after seven votes in favour during reflector poll. There were nine votes for P0 (Tentatively Ready), but also several for NAD Editorial, because 16.3.2.4 [structure.specifications]/7 explicitly says that all complexity requirements are upper bounds and it's conforming to do less work. The consensus was that this is still a clarifying improvement.

Proposed resolution:

This wording is relative to N5001.

1. Modify 26.8.6 [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.