Rearrange an array in place such that the first and last halves are interleaved

Question

Given an array of n elements in the following format { a1, a2, a3, a4, ….., an/2, b1, b2, b3, b4, …., bn/2 }. The task is shuffle the array to {a1, b1, a2, b2, a3, b3, ……, an/2, bn/2 } without using extra space.

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow, Each test case contains an integer n denoting the size of the array. The next line contains n space separated integers forming the array.

Output:

Print the shuffled array without using extra space.

Constraints:

1<=T<=10^5

1<=n<=10^5

1<=a[i]<=10^5

Example:

Input:

2

4

1 2 9 15

6

1 2 3 4 5 6

Output:

1 9 2 15

1 4 2 5 3 6

My approach:

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class ShuffleArray {

    private static int [] getShuffledArray (int[] arr) {
        //List <Integer> arrList = new ArrayList<>();

        return shuffleArray(arr,1,arr.length/2);
    }

    private static int [] shuffleArray (int[] arr, int swapInd1, int swapInd2) {
        if (swapInd2 == arr.length- 1) {
            return arr;
        }
        int temp = arr[swapInd2];

        for (int i = swapInd2 ; i > swapInd1; i--) {
            arr[i] = arr[i - 1];
        }

        arr[swapInd1] = temp;
        return shuffleArray(arr, swapInd1 + 2, swapInd2 + 1);
    }

    public static void main (String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int numTests = sc.nextInt();

            while (numTests-- > 0) {
                int size = sc.nextInt();
                int[] arr = new int[size];
                for (int i = 0; i < size; i++) {
                    arr[i] = sc.nextInt();
                }
                int[] soln = getShuffledArray(arr);
                for (int i = 0; i < soln.length; i++) {
                    System.out.print(soln[i] + " ");
                }
                System.out.println();
            }
        }
    }
}

I have the following questions with regards to the above code:

1. How can I further improve my approach?

2. Is there a better way to solve this question?

3. Are there any grave code violations that I have committed?

4. Can space and time complexity be further improved?

Reference

Answer 1

• The recursion results in \$O(n)\$ space complexity (each recursive invocation consumes some stack), so technically you did not fulfill the requirement of _not using extra space. Since it is a tail recursion, it can easy to eliminate. Unfortunately, Java doesn't do it, so you have to eliminate it manually. Fortunately, it is just a mechanical rewrite.

• The time complexity is \$O(n^2)\$. There is not much to do with the current approach. There is however a linear solution: an element at index k goes to either 2k, if k < n/2, or 2k - n + 1 otherwise. Convince yourself that this permutation has no loops, and just follow a chain of indices.

• The loop

  for (int i = swapInd2 ; i > swapInd1; i--) {
      arr[i] = arr[i - 1];
  }
  

  shifts a range, and deserves to be a function on its own (shift_rangeperhaps).