import java.util.*;
/** Given a Data Structure having first n integers and next n chars.
 * A = i1 i2 i3 ... iN c1 c2 c3 ... cN.
 * Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn
 *
 * Divide the array in four sections:[X,Y|A,B]
 * With swaps modify it to the form [X,A|Y,B].
 * Do recursion to solve [X|A] and [Y|B] separately, using divide and conquer.
 */
public class DivArr {

    private static int num=5;
    int arr[] = null;

    void swap(int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public int getK(int a[]) {
      int k = a.length;
      int j=0;
      for(; k>1; j++) {
        k = k >> 1;
      }
      for(k=1; j>0; j--) {
        k = k << 1;
      } // k is now the power of 2 <= a.length
      return k;
    }

    public void swapMiddle(int a[], int len) {
      swapMiddle(a, 0, len-1);
    }
    /* only handles powers of 2 */
    public void swapMiddle(int a[], int left, int right) {
        int diff = (right-left+1)/2;
        int mid = diff + left;
        int leftM = left+diff/2;  // middle of left side
        int rightM = mid+diff/2; // middle of right side
        if (leftM+1 >= rightM) return; // end cond
        int i=leftM; // i walks the left part
        int j=mid; // j walks the right part
        for (; i<mid; i++,j++) swap(i, j);
        // recursion on left side
        swapMiddle(a, left, mid);
        // recursion on left side
        swapMiddle(a, mid, right);
    }

    public static void main(String[] args) {
        DivArr inst = new DivArr();
        if (args.length>0) num= (new Integer(args[0])).intValue();
        inst.arr = new int[num];
        int k = inst.getK(inst.arr);
        System.out.println("k:"+k);
        int j=0;
        int mid= (k%2==0 ? k/2 : k/2+1);
        for (; j<mid; j++) inst.arr[j]=j;
        for (; j<k; j++) inst.arr[j]='A'+j-mid;
        System.out.println("\nin:");
        j=0;
        for (; j<mid; j++) {
          System.out.print(","+inst.arr[j]);
        }
        for (; j<k; j++) {
          System.out.print(","+(new Character((char)inst.arr[j])).toString());
        }
        System.out.println("\n");
        inst.swapMiddle(inst.arr, k); // pass reference so that it can do recursion
        System.out.println("\nout:");
        for (j=0; j<k; j++) {
          if (inst.arr[j] < 'A') {
            System.out.print(","+inst.arr[j]);
          } else {
            System.out.print(","+(new Character((char)inst.arr[j])).toString());
          }
        }
    }
}

k:64

in:
,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O
,P,Q,R,S,T,U,V,W,X,Y,Z,[,\,],^,_,`


out:
,0,A,1,B,2,C,3,D,4,E,5,F,6,G,7,H
,8,I,9,J,10,K,11,L,12,M,13,N,14,O,15,P
,16,Q,17,R,18,S,19,T,20,U,21,V,22,W,23,X
,24,Y,25,Z,26,[,27,\,28,],29,^,30,_,31,`

---