Heapsort implementation in C++14

Question

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

1. Have I correctly chosen the names InputIt and BidirIt for my iterators?
2. Is there a way to make the initialise iterator and then advance it pattern occupy one line instead of two?
3. Is the it != ix - 1 comparison of iterators ok?

Here is the code:

#include <iterator>
#include <functional>

template<
    class InputIt,
    class Key = std::less_equal<
        std::iterator_traits<InputIt>::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 < iy) {
        auto ir = il + 1;

        auto it = ir < iy && key(*ir, *il) ? ir : il;

        if (key(*ii, *it)) {return;}

        std::iter_swap(ii, it);
        std::     swap(ii, it);

        il = ix;
        std::advance(il, 2 * std::distance(ix, ii) + 1);
    }
}

template<
    typename BidirIt,
    typename Key = std::greater_equal<
        std::iterator_traits<BidirIt>::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);
    }
}

Answer 1

Answers:

1. 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.
2. Use std::next() as mentioned in the comment by user2296177.
3. 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<
    class InputIt,
    class Key = std::less_equal<
        std::iterator_traits<InputIt>::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.