2973. inplace_merge exact comparison count complexity prohibits useful real-world optimizations

Section: 26.8.6 [alg.merge] Status: LEWG Submitter: Billy Robert O'Neal III Opened: 2017-06-08 Last modified: 2020-09-06

Priority: Not Prioritized

View all other issues in [alg.merge].

View all issues with LEWG status.

Discussion:

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.

[2017-07 Toronto Monday issue prioritization]

Status to LEWG

Proposed resolution:

This wording is relative to N4659.

1. Edit 26.8.6 [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 (16.4.6.8 [algorithm.stable]).