Optimize algorithm arrange an array with items with even-indexs are on left side

Optimize algorithm arrange an array with items with even-indexs are on left side of array, items with odd-indexs are on right side of array

Requirement: using recursion, size of array is an even number.

For example:
0 1 2 3 4 5 (order of index)
a b c d e f (array before arrange)
a c e b d f (array after arrange)

0......1......2......3.....4......5.....6......7 (order of index)
a1....b1....a2....b2....a3....b3....a4....b4 (array before arrange)
a1....a2....a3....a4....b1....b2....b3....b4 (array after arrange)

The problem looks easy to solve if we dont care about optimization, we can use temp array or use recursion combine with a loop to shift items ... I think this way is not best solution ....I try to use recursion combine with swap operation, without using loop ... but I fail.

Hope someone suggests me an idea to resolve the problem, thanks any help

Quote:

---

Originally Posted by hongchanphat

or use recursion combine with a loop to shift items ... I think this way is not best solution

---

To recursively split the array into halves and re-arrange items would correspond to the idea behind quicksort.

And you could use sorting here. It's just to impose an ordering on the items and sort the array. Maybe that's cheating but it would give you an O(N * logN) solution. If you want better you must aim for O(N) which basically means you need to find a solution that scans the array a certain number of times independent of the number of items. This is not possible in the general case but since the array has a specific initial ordering this case may be an exception.