Hola.
Solo puedes hacerlo con ajax, bien puedes volver a cargar los datos (vía ajax) o si lo único que quieres es cambiar el orden puedes generar la tabla en html con php e implementar un ordenamiento con javascript como este, que utiliza
jQuery:
http://tablesorter.com/docs/#Demo
Saludos!