Heapsort implementation in C++14

Please review the following implementation of heapsort and pay attention to the following:

• Have I correctly chosen the names InputIt and BidirIt for my iterators?

• Is there a way to make the initialise iterator and then advance it pattern occupy one line instead of two?

• Is the it != ix - 1 comparison of iterators ok?

Here is the code:

#include 
#include 

template::value_type
    >
>
void plunge(
    const InputIt ix, // first element of heap
    const InputIt iy, // one-past last element of heap
    const InputIt iz, // element to be plunged
    Key key = Key()   // comparison key to use (up or down)
) {
    auto ii = iz;
    auto il = ix;
    std::advance(il, 2 * std::distance(ix, ii) + 1);

    while (il ::value_type
    >
>
void heapsort(const BidirIt ix, const BidirIt iy, Key key = Key()) {
    auto it = ix;
    std::advance(it, std::distance(ix, iy) / 2);

    for (; it != ix - 1; --it) {
        plunge(ix, iy, it, key);
    }

    for (it = iy - 1; it != ix - 1; --it) {
        std::iter_swap(ix, it);
        plunge(ix, it, ix, key);
    }
}

Answers:

• Input iterator is not suitable for your plunge function. The reason

is in std::advance(). It increments the iterators, which
invalidates all previous ones. Bidirectional iterators are ok.

• Use std::next() as mentioned in the comment by

user2296177.

• No. Only random access iterators are mandated to support the

operation.

Here is the piece of C++ 14 standard that proves answer #1.

Paragraph 24.2.3 of N4296 (Input Iterators). Note from table 107 - Input Iterator requirements (in addition to Iterator).

Expression:

++r;

pre: r is dereferenceable.
post: r is dereferenceable or
r is past-the-end.
post: any copies of the
previous value of r are no
longer required either to be
dereferenceable or to be in
the domain of ==.

where r is Input Iterator. Additionally, it is stated that post increment has the same effect. Either pre or post increment should be used to implement std::distance(), so it invalidates all copies of Input Iterators according to the standard.

Comments about the code

template::value_type
    >
>

Very arguable gain in readability.

Combo of first and last if preferred when referring to range. value is used to refer to some instance of T. ii and il make things even worse. Don't be lazy to type!

Bad idea to make iterators const. May be you wanted iterator pointing to const?

Nice usage of standard library (though you will need to be sure what it does, which you're trying to do).

The code is not working for input iterators, as mentioned in answers.

Nice one for the first try overall.

StackExchange Code Review Q#136286, answer score: 3