Move all odd positioned element to left half and even positioned to right half in-place

Question

Given an array with positive and negative integers, move all the odd indexed elements to the left and even indexed elements to the right.

The difficult part of the problem is to do it in-place while maintaining the order.

e.g.

7, 5, 6, 3, 8, 4, 2, 1

The output should be:

5, 3, 4, 1, 7, 6, 8, 2

If the order didn't matter, we could have been used partition() algorithm of quick sort.

How to do it in O( N )?

Answer 1

1. Get largest sub-array having size 3^k+1
2. 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 (even-indexed elements to the left of sub-array, odd-indexed - to the right), the replaced element should be also moved to its proper position, etc. until this procedure comes back to the starting position. This paper gives number-theoretic explanation why such selection of starting positions shuffles sub-array to the correct order.
3. Process the remaining parts of the array recursively, using steps 1 and 2.
4. Now we only need to join the reordered parts together. Start with the smaller sub-arrays at the end of the whole array. To exchange sub-array halves, use reverse algorithm: reverse(reverse(a), reverse(b)); or, for sub-array halves of equal size, use pair-wise swaps.
5. Now all even-positioned elements are on the left. To get them on the right, as required, exchange elements i and i+N/2 for all i = 0 .. N/2-1.

Algorithm is in-place, time complexity is O(N).

Example:

0 1 2 3 4  5 6 7 8 9   10 11 (the original array)
0 1 2 3 4  5 6 7 8 9 # 10 11 (split to sub-arrays)
0 2 4 3 8  1 6 5 7 9 # 10 11 (first cycle leader iteration, starting with 1)
0 2 4 6 8  1 3 5 7 9 # 10 11 (second cycle leader iteration, starting with 3)
0 2 4 6 8  9 7 5 3 1 # 10 11(2nd half of 1st part& 1st half of 2nd part reversed)
0 2 4 6 8 10 1 3 5 7    9 11 (both halves reversed together)

Variation of this algorithm, that does not need step 5:

• On step 1, get largest sub-array having size 3^k-1.
• On step 2, move even-indexed elements to the right of sub-array, odd-indexed - to the left. Use starting positions 0, 2, 8, ... 3^k-1-1 for cycle-leader algorithm.

Here is different O(N log N) in-place algorithm, which does not need number-theoretic proofs:

1. Reinterpret your array as a sequence of single-element 2*2 matrices, transpose these matrices.
2. Reinterpret the result as a sequence of two-element 2*2 matrices and transpose them.
3. Continue while matrices size is less than the array size.
4. Now we only need to join the reordered parts together (exactly as in previous algorithm).
5. Exchange elements of left and right halves of the array (exactly as in previous algorithm).

Example:

0  1   2 3   4 5   6 7  (the original array)
[0 2] [1 3] [4 6] [5 7] (first transposition)
[0 2] [4 6] [1 3] [5 7] (second transposition)

This problem is just a special case of the In-place matrix transposition.

Answer 2

I tried to implement as Evgeny Kluev said, and here is the result:

#pragma once

#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_;

};