Te explico un poco lo que hace el código de la página que has posteado.
Básicamente lo hace con DOM. Primero clona el nodo <tr> de la fila, y lo guarda en un array (según el orden ya ordenado).
Código PHP:
for(i=0;i<order.length;i++) mDiv[mDiv.length] = document.getElementsByTagName("tr")[order[i][1]].cloneNode(true);
Luego lo que hace es insertar esa fila antes de la última fila (document.getElementsByTagName("tr").length que yo sepa no es un índice válido, luego la referencia falla -al final de la tabla?)
Código PHP:
document.getElementsByTagName("tbody")[0].insertBefore(mDiv[z],document.getElementsByTagName("tr")[document.getElementsByTagName("tr").length]);
Después finaliza eliminando ciertas filas, que supongo que estarán duplicadas.
Podrías coger la idea de mover nodos de filas, creo que sería lo más óptimo e inteligente.
De hecho podrías hacer un sort(f) directamente, y en la función f ya movemos los nodos. Habría que hacer una función para intercambiar filas entre sí, y ya estaría todo hecho.
Sobre tu duda de si se puede hacer
tabla.getElementsByTagName('tr')[j].innerHTML=tabla.getElementsByTagName('tr')[j+1].innerHTML;
pues te diré que no lo sé, aunque no pinta mal en teoría, en la práctica, como dices tú, puede ser un poco bestia.
Un saludo.