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.

Answer 2

Ultimately I'm trying to simulate looping through the original array but skipping every other item and still looking each item.

In this case you do not need sorting at all: use a specialized stepper function that traverses odd indexes ahead of even indexes, or vice versa.

This approach works for any even value of N (the length of the array).

int N = 28;
Console.WriteLine("Odd before even");
for (var i = 1 ; i != N ; i = (i + 2) % (N+1)) {
    Console.Write("{0} ", i);
}
Console.WriteLine("Even before odd");
for (var i = 1 ; i != N ; i = (i + 2) % (N+1)) {
    // The formula is a bit complicated to avoid ternary:
    Console.Write("{0} ", -2*(i%2)+i+1);
}

Demo.

Answer 3

It's easy to sort an array with LINQ. To sort by odd/even, just return a value based on i % 2 from the predicate that you supply to OrderBy().

var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 );
Console.WriteLine(string.Join(",",sorted));

Output:

2,4,6,1,3,5

If you need sorted to be an array, just add ToArray():

var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 ).ToArray();
Console.WriteLine(string.Join(",",sorted));

And if you need the original array updated ("in place"), you can copy it back into the array like this:

var list = new int[] { 1, 2, 3, 4, 5, 6 };
var sorted = list.OrderBy( i => i % 2 );
sorted.Select( (n, i) => list[i] = n ).Last();
Console.WriteLine(string.Join(",",list));

Note that this solution requires the original array to be sorted. If it isn't, you can add the sort step with an additional LINQ call:

var list = new int[] { 6, 5, 4, 3, 2, 1 };
var sorted = list.OrderBy( i => i).OrderBy( i => i % 2 );
sorted.Select( (n, i) => list[i] = n ).Last();
Console.WriteLine(string.Join(",",list));

Answer 4

This turned out quite an interesting problem. First note that a trivial solution of O(N^2) is already posted, so now the question is whether we can do better.

My best attempt so far: just throw the odds and evens where you want them, then sort each half array.

static void swap<t>(ref T a, ref T b) {
    var temp = a;
    a = b;
    b = a;
}
static void ThrowInHalf<T>(T[] arr) {
    for (var i = 0 ; i < arr.Length/2; i+=2) {
        swap(arr[i],arr[L/2+i+1];
    }
}

After sorting all the evens should be in the second half, and the odds in the first. The problem breaks down such you get the exact same problem - even indices of the sub-array need to come before the odd ones, so you can run the algorithm again and so on, each time working on half an array, a classic O(nlog n). Of course, you could just re-sort each half array for the same run time cost (isn't as straight forward in c# as other languages, but there are options).

Other attempts at linear time

I tried two more things, but am stuck. The first:

static void sortAttempt1<T>(T[] array) {
    for(var i=0,inc=1; i+inc<array.Length; ++i) {
        swap(array[i],array[i+inc]);
        ++inc;
    }
}

This will get the first half like you want. I have yet to identify an algorithmic way to see how to re-order the second half, but it looks almost like there is a structure you can calculate and depends on what power of 2 is the length of the array.

Second attempt (A version of this I see was first posted by dasblinkenlight):

static int next(int i) {
    if(i&1)
        return i/2;
    return (L+i)/2;
}
static int cycle<T>(T[] array,int start) {
    var perms = 0;
    var keep  = array[start];
    var n     = next(start);
    while(n  != start) {
        swap(array[n],keep);
        n = next(n);
        ++perms;
    }
    return perms;
}
void sortAttempt2<T>(T[] array) {
    int perms = 0;
    for(int start = 0; perms<array.Length-1; start+=2) {
        perms += cycle(array,start);
    }
}

This solution runs cycles on the array. For example:

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

Starting at index 0, place the data exactly where you want it, then take what you just erased and put it where you want it, and so on, until you close a circle (the next function tells us exactly where an index should go):

0->4->6->7->3->1->0

Such that you get:

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

now run a cycle starting from index 2 (which is still in place)

2->5->2

sorting as we want in O(n). The problem is finding where to start the next cycle. start+2 works until an array of length 21, but after starts to fail on an increasing amount of inputs. I couldn't find an O(1) solution in both space and time to get the next iteration for the general case.

Summary of what I have

1. Solving this can be done in O(nlog n) time at least.
2. I provided two more attempts at an initial solution.

Anyone that has idea I would very much appreciate them. Including of course, a proof on a lower bound in time. Note suggestions to allocate an array of size that depends on N is strictly prohibited.

Answer 5

This will do an inplace sort:

static void SortOddEven<T>(T[] source)
{
    for (var start = 0; start < source.Length; start++)
    {
        for (var swap = start; swap < source.Length - start - 1; swap += 2)
        {
            var temp = source[swap];
            source[swap] = source[swap + 1];
            source[swap + 1] = temp;
        }
    }
}

And the corresponding even - odd sort is basically the same:

static void SortEvenOdd<T>(T[] source)
{
    for (var start = 1; start < source.Length; start++)
    {
        for (var swap = start; swap < source.Length - start; swap += 2)
        {
            var temp = source[swap];
            source[swap] = source[swap + 1];
            source[swap + 1] = temp;
        }
    }
}

Answer 6

You can try this, it is almost 3 times as fast as OrderBy/ToArray for an array with a million elements.

for (int i = 0; i < masiv.Length; i++)
        {
            if (i % 2 != 0) //or if (i % 2 == 0)
            {
                int j = i / 2;
                int tmp = masiv[i];
                masiv[i] = masiv[j];
                masiv[j] = tmp;
            }
        }
QuickSort(masiv, masiv.Length / 2, masiv.Length - 1);

//Quicksort method
public static void QuickSort(int[] a, int start, int end)
    {
        if (start >= end)
        {
            return;
        }

        int num = a[start];

        int i = start, j = end;

        while (i < j)
        {
            while (i < j && a[j] > num)
            {
                j--;
            }

            a[i] = a[j];

            while (i < j && a[i] < num)
            {
                i++;
            }

            a[j] = a[i];
        }

        a[i] = num;
        QuickSort(a, start, i - 1);
        QuickSort(a, i + 1, end);
    }

Answer 7

In a clarification I said that the ultimate result I was looking for was a way to iterate while skipping every other item.

I assumed an in-place sort would be the faster/cleaner approach, but in the end I just ended up extending List like this:

static class ListExtensions
{
    public static IEnumerable<T> GetEnumerableByOrderType<T>(this List<T> items, OrderType orderType)
    {
       int i = orderType == OrderType.SkipOffset && items.Count > 1 ? 1 : 0;

        int count = 0;
        while (i < items.Count)
        {
            yield return items[i];

            count++;

            i += orderType == OrderType.Default ? 1 : 2;

            if (count < items.Count && i >= items.Count)
            {
                i = orderType == OrderType.SkipOffset ? 0 : 1;
            }
        }
    }
}

public enum OrderType
{
    Default = 0,
    Skip, // Starts at 0
    SkipOffset // Starts at 1
}

Then I was able to simply change:

List<Move> moves = GetSortedMoves();
foreach (Move in moves)
{
    // Processing
}

to:

List<Move> moves = GetSortedMoves();
foreach (Move in moves.GetEnumerableByOrderType(OrderType.Skip))
{
    // Processing
}

It works with all three ordering types and with any size List.