Grailsort adversary pattern

grailsort_adversary.h++

struct grailsort_adversary:
    base_distribution<grailsort_adversary>
{
    template<typename RandomAccessIterator>
    static void reversal(RandomAccessIterator array, int start, int length)
    {
        for(int i = start ; i < start + ((length - start + 1) / 2) ; ++i) {
            std::swap(array[i], array[start + length - i]);
        }
    }

    template<typename RandomAccessIterator>
    static void rotate(RandomAccessIterator array, int a, int m, int b)
    {
        grailsort_adversary::reversal(array, a, m - 1);//reversal function is end inclusive
        grailsort_adversary::reversal(array, m, b - 1);
        grailsort_adversary::reversal(array, a, b - 1);
    }

    template<typename RandomAccessIterator>
    static void multiSwap(RandomAccessIterator array, int pos, int to)
    {
        if (to - pos > 0) {
            for (int i = pos ; i < to ; ++i) {
                std::swap(array[i], array[i + 1]);
            }
        } else {
            for (int i = pos ; i > to ; --i) {
                std::swap(array[i], array[i - 1]);
            }
        }
    }

    template<typename RandomAccessIterator>
    static void push(RandomAccessIterator array, int a, int b, int bLen)
    {
        int len = b - a,
             b1 = b - len % bLen,
             len1 = b1 - a;
        if (len1 <= 2 * bLen) return;

        int m = bLen;
        while (2 * m < len) m *= 2;
        m += a;

        if (b1 - m < bLen) {
            push(array, a, m, bLen);
        } else {
            m = a + b1 - m;
            grailsort_adversary::rotate(array, m-(bLen-2), b1-(bLen-1), b1);
            grailsort_adversary::multiSwap(array, a, m);//swaps item at a to m
            grailsort_adversary::rotate(array, a, m, b1);
            m = a + b1 - m;

            push(array, a, m, bLen);
            push(array, m, b, bLen);
        }
    }

    template<typename RandomAccessIterator>
    static void sort(RandomAccessIterator array, int start, int end)
    {
        auto min = array[start];
        auto max = min;
        for (int i = start + 1 ; i < end ; ++i) {
            if (array[i] < min) {
                min = array[i];
            }
            else if (array[i] > max) {
                max = array[i];
            }
        }

        auto size = max - min + 1;
        std::vector<int> holes(size);

        for (int i = start ; i < end ; ++i) {
            holes[array[i] - min] = holes[array[i] - min] + 1;
        }

        for (int i = 0, j = start ; i < size ; ++i) {
            while (holes[i] > 0) {
                holes[i] = holes[i] - 1;
                array[j] = i + min;
                ++j;
            }
        }
    }

    template<typename OutputIterator, typename Projection=cppsort::utility::identity>
    auto operator()(OutputIterator out, std::size_t size, Projection projection={}) const
        -> void
    {
        std::vector<int> vec;
        for (std::size_t i = 0 ; i < size ; ++i) {
            vec.emplace_back(i);
        }

        int block_size = 1;
        while (block_size * block_size < size) {
            block_size *= 2;
        }

        int nb_keys = (size - 1) / block_size + 1;
        int keys = block_size + nb_keys;

        std::shuffle(vec.begin(), vec.end(), distributions_prng);
        grailsort_adversary::sort(vec.begin(), 0, keys);
        reversal(vec.begin(), 0, keys - 1);
        grailsort_adversary::sort(vec.begin(), keys, size);

        grailsort_adversary::push(vec.begin(), keys, size, block_size);

        auto&& proj = cppsort::utility::as_function(projection);
        std::transform(vec.begin(), vec.end(), out, proj);
    }

    static constexpr const char* output = "grailsort_adversary.txt";
};