Reordenar datos de una tabla

[TheHard]

Saludos!

Tengo una consulta SQL, la cual me devuelve unos registros que yo despliego en una tabla, necesito que en cada registro de la tabla, poner un <input> donde el usuario ponga una prioridad (un número) y luego reordenar los datos de manera que aparezcan ordenados por la prioridad que le da el usuario... a alguien se le ocurre como hacer esto, o lo ha hecho antes?

Se me ocurre que después que el usuario ingrese la prioridad, almacenar los datos en alguna tabla temporal, pero tengo el problema que los datos son variables, y no sé si quedará muy pesada la página con esto, ya que cada vez que el usuario presione F5 tendría que borrar la tabla temporal y crearla de nuevo...

Alguna idea? Gracias!