Weaving an array

In preparing this answer, one of the components was an algorithm to rearrange a sorted array in a particular way. To put it succinctly, here's the problem description:


Given an array \$A\$ with \$n\$ elements \$A = \{ A_1, A_2, A_3, \dots , A_{n-2}, A_{n-1}, A_{n} \}\$ rearrange the contents such that the resulting array is \$A' = \{ A_1, A_n, A_2, A_{n-1}, A_3, A_{n-2}, \dots \}\$

I decided to create a templated function modeled on std::reverse that only uses two bidirectional iterators. Here's the templated function:

#include  

template
void weave(BidirIt first, BidirIt last) {
    if ((last - first) < 3) {
        return;
    }
    for (++first; first != last; ++first) {
        std::reverse(first, last);
    }
}

This is the code in context with a short test program.

testweave.cpp

#include 
#include 
#include 
#include 

std::ostream& operator& v) {
    if (v.begin() == v.end()) {
        return out 
void weave(BidirIt first, BidirIt last) {
    if ((last - first)  v;
    for (int i=0; i < 10; ++i) {
        std::cout << '\n';
        SHOW(v.size());
        SHOW(v);
        weave(v.begin(), v.end());
        SHOW(v);
        v.push_back(i);
        std::sort(v.begin(), v.end());
    }
}

I'm particularly interested in whether there is a more efficient algorithm for this.

Just glancing at it, this:

template
void weave(BidirIt first, BidirIt last) {
    if ((last - first) < 3) {
        return;
    }

...jumped out--although the template parameter seems to imply that you want this to work for bidirectional iterators, the subtraction will only work for a random access iterator. To work for bidirectional iterators, you'll want to use std::distance instead.

Although it's only in the test code:

std::ostream& operator& v) {
    if (v.begin() == v.end()) {
        return out << "{}";
    }

...I'd prefer if (v.empty()) {

As far as the algorithm goes, yes, there's better. In particular, it looks like your current algorithm is \$O(N^2)\$, but it's possible to do the job in \$O(N)\$ (as you probably expected).

The first step would be to reverse the entire second half of your input. From there you can use an in-place shuffle algorithm. Also see an old answer on SO.

StackExchange Code Review Q#123828, answer score: 6