move from right side to odd positions and from left side to even in-place

Question

Given a non-empty array of items. You have to move all the items from the right side to odd positions (zero-based), and from the left side — to even positions, as follows:

raw data: 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13

result: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

What in-place algorithm exists for this with O(n) time complexity? What is its implementation?

The inverse problem is solved here (this algorithm can be essentially inverted, but it will look ugly).

Answer 1

Here is only the algorithm itself. For details, explanations, and alternative approaches see answer for the inverse problem.

1. Initialize pointer to the pool of right-side elements to N/2.
2. Get largest sub-array having size 3^k+1
3. Join (3^k+1)/2 elements from the array's beginning and (3^k+1)/2 elements from the pool of right-side elements by exchanging appropriate sub-arrays. Update pool pointer.
4. Apply cycle leader algorithm to the parts of this sub-array, starting from positions 1, 3, 9, ... 3^k-1: move element to its proper position in sub-array (elements from the left of sub-array to even positions, from the right - to odd positions), the replaced element should be also moved to its proper position, etc. until this procedure comes back to the starting position.
5. Process the remaining parts of the array recursively, using steps 2 .. 4.

This problem is simpler than the inverse problem, referred in OP, because here we have to reorder sub-arrays starting from the larger ones, in the same order as doing cycle leader algorithm (the inverse problem has to do it separately and in reverse order, starting from the smaller ones to obtain O(N) complexity).

Answer 2

I finally found the solution of direct and inverse problems:

#include <iterator>
#include <algorithm>
#include <type_traits>
#include <limits>
#include <deque>
#include <utility>

#include <cassert>

template< typename Iterator >
struct perfect_shuffle_permutation
{

    static_assert(std::is_same< typename std::iterator_traits< Iterator >::iterator_category, std::random_access_iterator_tag >::value,
                  "!");

    using difference_type = typename std::iterator_traits< Iterator >::difference_type;
    using value_type = typename std::iterator_traits< Iterator >::value_type;

    perfect_shuffle_permutation()
    {
        for (difference_type power3_ = 1; power3_ < std::numeric_limits< difference_type >::max() / 3; power3_ *= 3) {
            powers3_.emplace_back(power3_ + 1);
        }
        powers3_.emplace_back(std::numeric_limits< difference_type >::max());
    }

    void
    forward(Iterator _begin, Iterator _end) const
    {
        return forward(_begin, std::distance(_begin, _end));
    }

    void
    backward(Iterator _begin, Iterator _end) const
    {
        return backward(_begin, std::distance(_begin, _end));
    }

    void
    forward(Iterator _begin, difference_type const _size) const
    {
        assert(0 < _size);
        assert(_size % 2 == 0);
        difference_type const left_size_ = *(std::upper_bound(powers3_.cbegin(), powers3_.cend(), _size) - 1);
        cycle_leader_forward(_begin, left_size_);
        difference_type const rest_ = _size - left_size_;
        if (rest_ != 0) {
            Iterator middle_ = _begin + left_size_;
            forward(middle_, rest_);
            std::rotate(_begin + left_size_ / 2, middle_, middle_ + rest_ / 2);
        }
    }

    void
    backward(Iterator _begin, difference_type const _size) const
    {
        assert(0 < _size);
        assert(_size % 2 == 0);
        difference_type const left_size_ = *(std::upper_bound(powers3_.cbegin(), powers3_.cend(), _size) - 1);
        std::rotate(_begin + left_size_ / 2, _begin + _size / 2, _begin + (_size + left_size_) / 2);
        cycle_leader_backward(_begin, left_size_);
        difference_type const rest_ = _size - left_size_;
        if (rest_ != 0) {
            Iterator middle_ = _begin + left_size_;
            backward(middle_, rest_);
        }
    }

private :

    void
    cycle_leader_forward(Iterator _begin, difference_type const _size) const
    {
        for (difference_type leader_ = 1; leader_ != _size - 1; leader_ *= 3) {
            permutation_forward permutation_(leader_, _size);
            Iterator current_ = _begin + leader_;
            value_type first_ = std::move(*current_);
            while (++permutation_) {
                assert(permutation_ < _size);
                Iterator next_ = _begin + permutation_;
                *current_ = std::move(*next_);
                current_ = next_;
            }
            *current_ = std::move(first_);
        }
    }

    void
    cycle_leader_backward(Iterator _begin, difference_type const _size) const
    {
        for (difference_type leader_ = 1; leader_ != _size - 1; leader_ *= 3) {
            permutation_backward permutation_(leader_, _size);
            Iterator current_ = _begin + leader_;
            value_type first_ = std::move(*current_);
            while (++permutation_) {
                assert(permutation_ < _size);
                Iterator next_ = _begin + permutation_;
                *current_ = std::move(*next_);
                current_ = next_;
            }
            *current_ = std::move(first_);
        }
    }

    struct permutation_forward
    {

        permutation_forward(difference_type const _leader, difference_type const _size)
            : leader_(_leader)
            , current_(_leader)
            , half_size_(_size / 2)
        { ; }

        bool
        operator ++ ()
        {
            if (current_ < half_size_) {
                current_ += current_;
            } else {
                current_ = 1 + (current_ - half_size_) * 2;
            }
            return (current_ != leader_);
        }

        operator difference_type () const
        {
            return current_;
        }

    private :

        difference_type const leader_;
        difference_type current_;
        difference_type const half_size_;

    };

    struct permutation_backward
    {

        permutation_backward(difference_type const _leader, difference_type const _size)
            : leader_(_leader)
            , current_(_leader)
            , half_size_(_size / 2)
        { ; }

        bool
        operator ++ ()
        {
            if ((current_ % 2) == 0) {
                current_ /= 2;
            } else {
                current_ = (current_ - 1) / 2 + half_size_;
            }
            return (current_ != leader_);
        }

        operator difference_type () const
        {
            return current_;
        }

    private :

        difference_type const leader_;
        difference_type current_;
        difference_type const half_size_;

    };

    std::deque< difference_type > powers3_;

};