Java - Ejercicio matrices

Saludos a todos!

Quisiera su ayuda con el siguiente ejercicio:

Crear una matriz A de dimensiones n*m con valores enteros que son ingresados por el usuario. Se desea construir un algoritmo que copie todos los valores de la matriz a un vector, luego los ordene de la siguiente manera:
a. Los valores pares deben quedar en la primera mitad del vector(ordenados ascendentemente).
b. Los valores impares deben quedar en la segunda mitad del vector (ordenados ascendentemente).

....pues bien....resulta que el algoritmo que tengo desarrollado me hace gran parte, pero estoy usando dos vectores para guardar los valores pares y otro vector para los valores impares, y el ejercicio pide que sea en uno solo. Según he consultado esto se hace con el método de ordenación por inserción, sin embargo no entiendo como? si pueden ayudarme, seria de mucha ayuda, aquí el código de Jcreator:

import java.io.*;
import java.util.Scanner;
public class MatrizParImp
{
public static void main(String[] args)
{

Scanner entrada = new Scanner (System.in);

int x[][], par[], imp[], n, m, i, j, k=-1, r=-1, s;
System.out.print("Ingrese el numero de filas matriz X:");
n = entrada.nextInt();
System.out.print("Ingrese numero de columnas matriz X:");
m = entrada.nextInt();
x = new int[n][m]; par = new int[n*m]; imp = new int [n*m];
for (i=0;i<n;i++){
for (j=0;j<m;j++){
System.out.print("Ingrese valor en la posicion ["+i+"]["+j+"]:");
x[i][j] = entrada.nextInt();
}
}
for (i=0;i<n;i++){
for(j=0;j<m;j++){
if (x[i][j]%2==0){
s=0;
while (x[i][j]!=par[s] && s <= k){
s++;
}
if(s>k){
k++;
par[k] = x[i][j];
}
}
else{
s=0;
while (x[i][j]!=imp[s] && s<=r){
s++;
}
if(s>r){
r++;
imp[r] = x[i][j];
}
}

}
}
System.out.print("\n\nVector de pares: ");
for (i=0;i<=k;i++){
System.out.print(+par[i]+",");
}
System.out.print("\n\nVector de impares: ");
for (i=0;i<=r;i++){
System.out.print(+imp[i]+",");
}

}


}