Suppose we need to sort a sequence and we know that every sequence component is within \$d\$ steps from its correct position. In such a case we can use a local heapsort: we take \$d\$ as an argument and set \$w = d + 1\$ (window width). We load the heap with \$w\$ first sequence components after which we pop the heap and add the next component to the heap (a sliding window). Finally, we dump the leftovers to the end of the range to be sorted:local_heapsort.hpp// Created Apr 5, 2017 by Rodion rodde Efremov#ifndef CODERODDE_UTIL_LOCAL_HEAPSORT#define CODERODDE_UTIL_LOCAL_HEAPSORT#include <algorithm>#include <iterator>#include <queue>#include <vector>namespace coderodde {    namespace util {        template<typename RandomIt, typename Cmp>        void local_heapsort(RandomIt begin,                            RandomIt end,                            Cmp cmp,                            size_t max_distance)        {            using value_type =            typename std::iterator_traits<RandomIt>::value_type;            size_t range_distance = std::distance(begin, end);            max_distance = std::min(max_distance, range_distance);            size_t window_width = max_distance + 1;            auto window_end = begin;            std::advance(window_end, window_width);            std::priority_queue<value_type, std::vector<value_type>, Cmp> heap;            auto current_iterator = begin;            auto next_iterator = begin;            std::advance(next_iterator, window_width);            for (auto iter = current_iterator; iter != next_iterator; ++iter)            {                heap.push(*iter);            }            while (next_iterator != end)            {                *current_iterator = heap.top();                heap.pop();                heap.push(*next_iterator);                ++current_iterator;                ++next_iterator;            }            while (!heap.empty())            {                *current_iterator = heap.top();                heap.pop();                ++current_iterator;            }        }    } // End of namespace coderodde::util} // End of namespace coderodde#endif // CODERODDE_UTIL_LOCAL_HEAPSORTmain.cpp#include local_heapsort.hpp#include <algorithm>#include <chrono>#include <iostream>#include <iterator>#include <random>#include <vector>using namespace std;using namespace std::chrono;using coderodde::util::local_heapsort;static void small_demo(){    cout << Sorting: ;    vector<int> vec = { 3, 2, 1, 5, 4, 8, 7, 6 };    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout,  ));    cout << endl;    local_heapsort(vec.begin(), vec.end(), std::greater<int>(), 2);    cout << Sorted:  ;    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout,  ));    cout << endl;}static const size_t ARRAY_LENGTH = 50 * 1000 * 1000;static const size_t MAX_DISTANCE = 10;static vector<int> get_random_int_array_with_max_distance(size_t array_length,                                                          size_t max_distance){    vector<int> ret(array_length);    for (int i = 0; i < array_length; ++i)    {        ret[i] = i;    }    // Shuffle small chunks in such that any array component is at most    // 'max_distance' position from its eventual position:    size_t chunk_size = max_distance + 1;    random_device rd;    mt19937 g(rd());    for (size_t i = 0; i < array_length; i += chunk_size)    {        shuffle(&ret[i], &ret[min(i + chunk_size, array_length)], g);    }    return ret;}static void benchmark(){    vector<int> array1 = get_random_int_array_with_max_distance(ARRAY_LENGTH,                                                                MAX_DISTANCE);    vector<int> array2(array1);    auto tp1 = high_resolution_clock::now();    // For fairness, we pass the same comparator to std::sort    //as to local_heapsort.    sort(array1.begin(), array1.end(), std::less<int>());    auto tp2 = high_resolution_clock::now();    cout << std::sort in          << duration_cast<milliseconds>(tp2 - tp1).count()         <<  milliseconds.         << endl;    tp1 = high_resolution_clock::now();    local_heapsort(array2.begin(),                   array2.end(),                   std::greater<int>(),                   MAX_DISTANCE);    tp2 = high_resolution_clock::now();    cout << local_heapsort in          << duration_cast<milliseconds>(tp2 - tp1).count()         <<  milliseconds.         << endl;    cout << Algorithms agree:          << boolalpha         << equal(array1.begin(),                  array1.end(),                  array2.begin())         << endl;}int main() {    small_demo();    benchmark();    return 0;}Performance figuresMy demo program gives the following output:Sorting: 3 2 1 5 4 8 7 6 Sorted:  1 2 3 4 5 6 7 8 std::sort in 1845 milliseconds.local_heapsort in 1359 milliseconds.Algorithms agree: trueCritique requestPlease tell me anything that comes to mind. Especially, I wish to know how to make my code more idiomatic; say, is there opportunity to replace some explicit loops with facilities from <algorithm>?
Local heapsort in C++
c++;algorithm;c++11;sorting;heap sort
Bug:I found this post, which says that if Cmp is a function pointer, priority_queue will default construct it to nullptr, which is straight undefined behavior. So, passing cmp into priority_queue becomes a must.I believe that idiomatic code is the code that conforms C++ concepts, so I will try to cover those as well.Formal specification:I believe the formal specification is the best thing to check conformance.From the names of template type parameters I inferred following C++ concepts:RandomAccessIteratorCompare = BinaryPredicate + semanticsCopyConstructible (may be other requirements on element type)Code has good conformance, except Compare. If you'll follow long chain of links on cppreference, at the end it becomes clear that BinaryPredicate is ought to be only CopyConstructible. The priority_queue will try to default construct it, which is a violation of concept. The fix would be just to pass the cmp into constructor. Fortunately, there is a constructor that takes just Compare and container defaulted to default constructed container (not that there is abundance of constructors).Shortcut:Every time iterator is created and std::advance() is used, it is possible to just create and initialize using std::next(). Instead of:auto iterator = another_iterator;std::advance(iterator, distance);could be:auto iterator = std::next(another_iterator, distance);Default comparison:It is possible to use default type for the type parameter. Unfortunately in C++11 declaration will be pretty long:    template<typename RandomIt,              typename Cmp =                       typename std::less<std::iterator_traits<RandomIt>::value_type>>    void local_heapsort(RandomIt begin,                        RandomIt end,                        size_t max_distance,                        Cmp cmp = {})Though it is possible to make specialization in std until switching to newer C++ version. In C++14 it would be just typename Cmp = std::less<>.Minor feature:I believe the container type should be also a template parameter, but a last, defaulted to vector, one. In some cases people could deploy sophisticated allocators.Smaller things:Usually begin and end are named first and last.The algorithm could check the size of the first window, so if the range would have small length, the code wouldn't invoke undefined behavior. I believe the decrease maintenance cost will outweigh decrease in performance (which probably won't be visible). If there would be some function to get/check the window length or guidelines documented somewhere, may be check could be removed.You could try to detach the sliding window into own function. I tried it, but the result was not-good-not-bad, which is kind of weird. It also has strong coupling with my transform iterator, which is not great. So, better design is certainly needed.The main.cpp is a total carnage, but the static keyword on each function got my special attention. It doesn't look like it is needed. Is it an artifact of writing primarily Java? :)