EvenOddSort

public void evenOdd(int[] A) {
  // [0: even - 1] // even
  // [even: odd] // unsorted
  // [odd + 1: A.length - 1] // odd
  int even = 0;
  int odd = A.length - 1;
  while (even <= odd) {
    if (A[even] % 2 == 0) {
      even++;
    } else {
      swap(A, even, odd);
      odd--;
    }
  }
}

private void swap(int[] A, int i, int j) {
  int t = A[i];
  A[i] = A[j];
  A[j] = t;
}