# 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<=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

• 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).

• Thanks for your suggestions. If I may ask, how is the space complexity O(n)? Do you refer to the continuous reallocation and shifting of the array? – Anirudh Thatipelli Sep 2 '18 at 3:49