Local heapsort in C++

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
#include
#include
#include

namespace coderodde {
namespace util {

template
void local_heapsort(RandomIt begin,
RandomIt end,
Cmp cmp,
size_t max_distance)
{
using value_type =
typename std::iterator_traits::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, 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;
}

@Incomputable already said most of what I was going to say. So this is not as much an answer as it is curious fact.

Seeing your problem formulation, I remembered one thing from my CS classes, many years ago:


Bubble Sort (and it's friend, Shaker Sort) is fast!... When the data is almost sorted.

And this is exactly the case you have, so I implemented Shaker Sort (which is simply Bubble sort but you bubble both ways) and compared it to your Local Heapsort:

template
void shakersort(RandomIt begin, RandomIt end, Cmp cmp){
  auto changed = true;
  while(changed){
    changed = false;
    auto prev = begin;
    auto next = std::next(prev);

    while(next != end){
      if(cmp(*prev, *next)){
        using std::swap;
        swap(*next, *prev);
        changed=true;
      }
      next = std::next(next);
      prev = std::next(prev);
    }

    if(changed){
      changed = false;
      prev = std::prev(prev);
      next = std::prev(next);
      while(prev != begin){
        if(cmp(*prev, *next)){
          using std::swap;
          swap(*next, *prev);
          changed=true;
        }
        prev = std::prev(prev);
        next = std::prev(next);
      }
      if(cmp(*prev, *next)){
        using std::swap;
        swap(*next, *prev);
        changed=true;
      }
    }       
  }
}

Please excuse the code duplication, I'm not asking for a review ;)

And when I run it on my machine:

~ $ g++ -march=native -O3  --std=c++14 main.cpp && ./a.out 
Sorting: 3 2 1 5 4 8 7 6 
Sorted:  1 2 3 4 5 6 7 8 
Shakersort in 859 milliseconds.
local_heapsort in 987 milliseconds.
Algorithms agree: true

It turns out that although your algorithm is faster than std::sort, Shaker Sort is even faster in this case. This is also the reason that you use Shaker Sort in the final stages of Quick Sort when the ranges get small.

StackExchange Code Review Q#159938, answer score: 4