Rearrange an array in place such that the first and last halves are interleaved 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&lt;=T&lt;=10^5 
  
  1&lt;=n&lt;=10^5 
  
  1&lt;=a[i]&lt;=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 &lt;Integer&gt; arrList = new ArrayList&lt;&gt;();

        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 &gt; 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-- &gt; 0) {
                int size = sc.nextInt();
                int[] arr = new int[size];
                for (int i = 0; i &lt; size; i++) {
                    arr[i] = sc.nextInt();
                }
                int[] soln = getShuffledArray(arr);
                for (int i = 0; i &lt; soln.length; i++) {
                    System.out.print(soln[i] + " ");
                }
                System.out.println();
            }
        }
    }
}


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


How can I further improve my approach?
Is there a better way to solve this question?
Are there any grave code violations that I have committed?
Can space and time complexity be further improved?


Reference
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 &lt; 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 &gt; swapInd1; i--) {
    arr[i] = arr[i - 1];
}


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