In preparing [this answer](https://codereview.stackexchange.com/questions/123713/custom-card-game/123779#123779), 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 <algorithm> 

template<class BidirIt>
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 <utility>
#include <algorithm>
#include <iostream>
#include <vector>

std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
    if (v.begin() == v.end()) {
        return out << "{}";
    }
    out << "{" << *v.begin();
    for (auto it = v.begin()+1; it != v.end(); ++it) {
        out << ", " << *it;
    }
    return out << "}";
}

#define SHOW(x) std::cout << # x " = " << x << '\n'

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

int main()
{
    std::vector<int> 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.