He encontrado una solución con una única pasada: recorro el array y si encuentro un 1 lo pongo en un lado (el inicio del array), si encuentro un tres lo pongo en en el otro extremo (al final). Cuando he terminado los 2 están todos en medio:
const log= console.log;
function sort(array) {
let index1 = 0;
let index3 = array.length - 1;
for (let i = 0; i <= index3; i++) {
if (array[i] === 3) {
if (i < index3) {
while(array[index3] ===3 && index3 > i) {
index3--; //cada paso de este bucle, reduce en un paso el for
}
log('moviendo 3 a', index3);
let aux = array[index3];
array[index3] = array[i];
array[i] = aux;
}
index3--;
}
if (array[i] === 1) {
if (i > index1) {
log('moviendo 1 a', index1);
let aux = array[index1];
array[index1] = array[i];
array[i] = aux;
}
index1++;
}
}
return array;
}
console.log(sort([1,2,3,1,2, 3,1,2,3,2, 2,2,3,3,3, 1,1]).toString());
console.log(sort([1,3,1,3,3,3,1,1,3,3,3,1]).toString());
console.log(sort([1,1,3,2,1, 3,1,1,3,1, 1,1,1,1,1, 1,1]).toString());
log(sort([2,3,3,3,3,3,3,3,3,3, 3,3,3,3,3, 3,1]).toString())