io farei una cosa al posto tuo(nn penso che conosci arraycopy vero?)

allora istanzio 2 nuovi array un per i pari ed uno per i dispari, il problema è però vedere quanti pari ci sono e quanti dispari...


allora usiamo la via più semplice ma anche la più lunga...

int pari =0;
int dispari = 0;
for(int i = 0 ; i<arrayutente.length; i++)
if((arrayutente[i] % 2) == 0)
pari++;
else
dispari++;

in questo modo ti crei le dimensioni dei due nuovi array

int [] arraypari = new int[pari];
int [] arraydispari = new int[dispari];

rifai un ciclo for come quello precendente solo che a posto degli incrementatori,copi l'elemento i esimo nel suo array.

ora se passi un numero di elementi pari questi 2 vettori hanno la stessa lunghezza,se invece sono dispari,uno dei 2 sarà più grande di uno...

allora ti fai un altro controllo
if(pari.length==dispari.length)
for(int i =0;i<pari.length;i++)
System.out.print(pari[i]+" "+dispari[i]+" ");
if(pari.length>dispari.length)
System.out.print(pari[i]+" ");
for(int i=0;i<dispari.length;i++)
System.out.print(dispari[i]+" "+pari[i+1]+" ");
if(rifai lo stesso metodo di sopra solo che è nel caso che dispari sia più grande di pari...)


l'ho buttato così adesso,dovrebbe funzionare in caso provalo e fai le dovute modifiche ^^
inoltre è fortemente ottimizabile ma è una cosa che lascio fare a te in caso