How can I re-sort an array in-place to put the even indexed items before the odd?

Question

I have a sorted array that I want to re-sort such that the previously even indexed items are at the beginning, followed by the odd indexed items.

Ex: [a, b, c, d, e, f] => [a, c, e, b, d, f].

I'll also (separately) want to do the opposite, with odd indexes first:

Ex: [a, b, c, d, e, f] => [b, d, f, a, c, e].

I know I could create separate odd/even arrays then re-merge them, but performance is key and I'm trying to find a single-loop, in-place solution that avoids allocating and using temporary arrays.

Context:

I'm recursively searching a game tree of moves (minimax with alpha-beta) and am trying to implement Lazy SMP, where I search the same positions on other threads but try the moves in slightly different orders, saving results to a shared (transposition) table, to boost the efficiency of the primary search thread.

Clarifications:

The starting array has already been sorted and I want the order within the even/odd indexes to be maintained. Ie., I don't want to just group the evens and odds together and end up with say [f, b, d, e, c, a].

Also, I'm sorting strictly by the index value, not the item stored there. So any methods that involve search predicates on the item value won't work.

And though I'm writing in C# I don't want to use LINQ as I need the code to be portable to systems without LINQ.

I'm hoping there's a way to loop though the array once and perform a series of item swaps such that I end up with ordering I've described. I've been trying it on paper but haven't gotten anything to work yet.

Clarifications 2:

I've updated the examples with letters instead of numbers, and swapped the odd/even examples as I got them backwards. I want both.

Ultimately I'm trying to simulate looping through the original array but skipping every other item and still looking each item. With two loops I'd do the following:

// Case 1: Regular order
for (int i = 0; i < items.Length; i ++)
{
    // Process
}


// Case 2: Even indexes first
for (int i = 0; i < items.Length; i += 2)
{
    // Process
}

for (int i = 1; i < items.Length; i += 2)
{
    // Process
}


// Case 3: Odd indexes first
for (int i = 1; i < items.Length; i += 2)
{
    // Process
}

for (int i = 0; i < items.Length; i += 2)
{
    // Process
}

The processing within the loop is complicated enough as it calls this function recursively, has separate conditions for terminating the loop early, etc, so I don't want to duplicate it and/or put it within another function.

So rather than having two loops, or one complicated loop that handles all three cases, I'd rather just presort the items.

Clarifications 3:

I need something that handles all three cases, that supported any size array (not just even # of items), and didn't clutter the game search loop contents. I thought doing an in-place pre-sort before that loop was the best option.

In the end I decided to abandon the in-place pre-sort and extend List with a custom iterator that skips items. I added my code below, though I won't mark it as the answer as it technically isn't what I asked for.

Thanks for everyone's help. (And if someone does post a single loop, in-place swap based solution that works for any number of items I'll be glad to accept it as the answer.)

Answer 1

Here is an algorithm that does it in a single path over the array. It assumes that the array has an even number of items N, and that we can allocate bool[N/2] array:

static void OddEvenSwap(int[] data) {
    int n = data.Length / 2;
    int p = 0;
    var seen = new bool[n];
    while (true) {
        int last = data[p];
        do {
            var tmp = data[p];
            data[p] = last;
            last = tmp;
            if (p < n) {
                seen[p] = true;
            }
            p = (p/2) + (p%2 == 0 ? n : 0);
        } while (p >= n || !seen[p]);
        data[p] = last;
        while (p != n && seen[p]) {
            p++;
        }
        if (p == n) {
            break;
        }
    }
}

Here is a brief explanation of how it works:

• Given a source index p of an item, we can always compute its destination index directly
• Start at index zero, compute its destination index, move the item there, and continue from the destination index to the next destination
• Mark all indexes in the lower half that we have visited
• Eventually we will come around to the index that we've seen; place the last item there, because we've finished the cycle
• Find the next index from the lower half that we have not visited yet
• Once we've exhausted all indexes, we are done

Demo.

Note: If you run this algorithm repeatedly, you should be able to avoid re-allocation of seen[] array by allocating it once at the max size, and then simply filling it in with falses.