pattern of recursively splitting an array to odd and even elements

Question

I am looking to find a pattern to recursively split an array to odd and even elements. I will try to describe the problem in the following:

suppose we have an array of length 16 as:

a=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

First iteration: splitting in odd and even

[0,2,4,6,8,10,12,14]
[1,3,5,7,9,11,13,15]

which basically are

a[2i]   for i=0:7
a[2i+1] for i=0:7

splitting each of these arrays into odd and even elements again we have

[0,4,8,12]
[2,6,10,14]
[1,5,9,13]
[3,7,11,15]

that similarly are

4i    for i=0:3
4i+2
4i+1
4i+3

splitting again the array elements would be

[0,8]
[4,12]
.
.
[1,9]

or

8i    for i=0:1
8i+4
8i+2
8i+6
8+1
8i+5
8i+3
8i+1

Arrays needed to split recursively until each array has only two elements.

One things that I noticed that the bottom half is similar to the top one and we just need to add "1" to the index terms

I was wondering how Can I find the pattern for an array with an "n" elements?

Thank you very much for your time.

Answer 1

assuming your number n is a power of 2 (aka 2^k):

then you will have m = n/2 = 2^(k-1) arrays with following numbers for i in {0,1}:

0: m*i+f(0)
1: m*i+f(1)
...
j: m*i+f(j)
...
m-1: m*i+f(m-1)

where f(x) is a function which takes an integer (x), transforms it into an k-1-bit binary number (b), reverses it (rb) and returns its decimal value (y).

Example for k=4 (which looks a lot like your values):

x	b	rb	f(x)=y
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7