Hola,
Perdón por haberme adelantado un poquito ... (aunque no estaba seguro si ibas a continuar, por eso no lo había mostrado) ... lo divido en 3 partes ...
1. Parte.
Unas cuantas correcciones que encontré analizandolo un poco más detenidamente,
Cita:
Iniciado por HackmanC 
Código PHP:
$orden[0]="0_0_0";
$orden[1]="0_1_0";
$orden[2]="1_0_0";
$orden[3]="2";
$orden[4]="2_0_5";
$orden[5]="2_0_6";
$orden[6]="5";
$orden[7]="5_2";
$orden[8]="6";
$orden[9]="6_1";
$orden[10]="6_1_0";
$orden[11]="6_1_1";
$orden[12]="6_2_0";
Yo agregué mas elementos al final porque me pareció que al ejemplo que pusiste le hacían falta,
Al ver bien los datos, ¿Que debería pasar al desaparecer el $orden[8]="6"?, es algo que tienes que tomar en cuenta y no había contemplado anteriormente.
Cita:
Iniciado por HackmanC 3. first pass - recursive
Mover todos los que coincidan en el nivel 1.
Barrer el array, todos los que coincidan con un nivel superior (1 elemento) moverlos hacia adentro sub-array.
Aquí hay un error, no podría ser 1 elemento (por el motivo anterior), tendría que ser 'todos los que coincida exactamente en la misma cantidad de elementos con el anterior'.
Y lo de moverlos suena complicado, mejor sería crear un nuevo array temporal donde se van copiando y agregando, y es lo que devuelve la función recursiva.
Cita:
Iniciado por HackmanC 4. second pass
Mover todos los que coincidan en el nivel 2.
Esta es la parte recursiva, entra en la misma función anterior, pero solamente pasa como parámetros el sub-array, pasar por referencia.
Ya no verifica igualdad de 1 elemento, sino 2.
También el mismo error anterior, no verifica 2 elementos, verifica 'todos los elementos que coincidan exactamente con el nivel superior'.
Como devuelve un array temporal no es necesario pasar por referencia.
Cita:
Iniciado por HackmanC 6. Renumerar - recursiva
7. Posiblemente extraer a un nuevo array plano; barrer recursivamente y agregar al final de un array global.
Esta operación sería adecuado realizarla de una sola pasada recursivamente, no 2 funciones diferentes.
Saludos,