This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++20 status.

### 2444. Inconsistent complexity for `std::sort_heap`

Section: 25.8.8.5 [sort.heap] Status: C++20 Submitter: François Dumont Opened: 2014-10-07 Last modified: 2021-02-25

Priority: 3

View all issues with C++20 status.

Discussion:

While creating complexity tests for the GNU libstdc++ implementation I stumbled across a surprising requirement for the `std::sort_heap` algorithm.

In 25.8.8.5 [sort.heap] p3 the Standard states:

> Complexity: At most `N log(N)` comparisons (where `N == last - first`).

As stated on the libstdc++ mailing list by Marc Glisse `sort_heap` can be implemented by `N` calls to `pop_heap`. As max number of comparisons of `pop_heap` is `2 * log(N)` then `sort_heap` max limit should be `2 * log(1) + 2 * log(2) + .... + 2 * log(N)` that is to say `2 * log(N!)`. In terms of `log(N)` we can also consider that this limit is also cap by `2 * N * log(N)` which is surely what the Standard wanted to set as a limit.

This is why I would like to propose to replace paragraph 3 by:

> Complexity: At most `2N log(N)` comparisons (where `N == last - first`).

[2015-02 Cologne]

Marshall will research the maths and report back in Lenexa.

[2015-05-06 Lenexa]

STL: I dislike exact complexity requirements, they prevent one or two extra checks in debug mode. Would it be better to say O(N log(N)) not at most?

[2017-03-04, Kona]

Move to Tentatively Ready. STL may write a paper (with Thomas & Robert) offering guidance about Big-O notation vs. exact requirements.

Proposed resolution:

This wording is relative to N3936.

1. In 25.8.8.5 [sort.heap] p3 the Standard states:

   >     template<class RandomAccessIterator>
   >       void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
   >     template<class RandomAccessIterator, class Compare>
   >       void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
   >                      Compare comp);

   > > […]

   > > -3- Complexity: At most `2N log(N)` comparisons (where `N == last - first`).