Java – cut and stack arrays

I have an int array as input The length of the array is always 2 ^ n. I want to cut the array in half and stack it Repeat cutting and stacking until there is only one stack For example:

int [] array = {1,2,3,4,5,6,7,8}

If we cut the arrays in half and stack them, they will be:

{1,| 3,4}
{5,| 7,8}

Cut it open and stack it again:

{1,|2}
{5,|6}
{3,|4}
{7,|8}

Again:

{1}
{5}
{3}
{7}
{2}
{6}
{4}
{8}

The desired output will be an int array from the top to the end of the stack

int[] output =  {1,8}

I tried to construct an output array by looping through the input array in a specific way Please note that when I reach the array, I start with my head again I start with the array [i], where I = 0 I got the first number like this Then I add I times N, where n is log (array. Legnth) (base 2) This is how I get the second number For the third number, we increment I (n / 2) For the fourth number, we add I. I wonder if there is a pattern? Or what is your solution to this problem? I am looking for a Java or Python solution

Edit / update:

I tried a new way to use queues I basically cut the array in half and push the two halves of the array into the queue until the array in the queue is 2 in length (or the stack is at height n) But my result is not correct I think it has something to do with the order in which I add half arrays back to the queue

import java.util.*;

public class StackArray{
    public static void main(String[] args){
        int[] array = {1,8};
        int[] answer = stackArray(array);
        for(int n : answer){
            System.out.println(n);
        }   
    }   

    public static int[] stackArray(int[] array){
        int height = (int) (Math.log(array.length)/Math.log(2)) + 1;
        Queue<int[]> queue = new LinkedList<int[]>();
        ArrayList<Integer> list = new ArrayList<>();
        queue.add(array);
        while(queue.size() < height){
            int currentLength = queue.size();
            int i = 0;
            while(i < currentLength){
                int[] temp = queue.poll();
                int[] array1 = new int[temp.length/2];
                int[] array2 = new int[temp.length/2];
                System.arraycopy(temp,array1,array1.length);
                System.arraycopy(temp,array1.length,array2,array2.length);
                queue.add(array1); //I think the problem is here
                queue.add(array2);
                i++;
            }

        }


        int y = 0;
        while(y < 2){

            for(int i = 0; i < queue.size(); i++){
                int[] curr = queue.poll();
                list.add(curr[y]);
                queue.add(curr);

            }
            y++;
        }

        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            ret[i] =list.get(i);
        }

        return ret;

    }
}

result:

1
3
5
7
2
4
6
8

How can I solve this problem?

Update: I solved it and released my own answer But I'm still curious about how others can solve this problem Please feel free to answer

Solution

I think if you use a 0-based index, the pattern will become clear

0    1    2    3    4    5    6   7
      000  001  010  011  100  101  110  111

       0    1    2    3
      000  001  010  011
      100  101  110  111
       4    5    6    7


  0 = 000  001 = 1 
  4 = 100  101 = 5
  2 = 010  011 = 3
  6 = 110  111 = 7

  0 = 000  
  4 = 100
  2 = 010
  6 = 110
  1 = 001
  5 = 101
  3 = 011
  7 = 111

See the leftmost bit pattern? The order is the number 0,1,2 The order of bits is reversed