lo que puedes hacer es tener un parametro, digamos orden, que de existir indica por que columna ordenas la consulta, entonces si este parametro existe modificas el query (supongamos que esta en la variable $consulta), adecuandolo a lo que tienes que hacer, algo asi
Código:
if(isset($orden))
{
$consulta .= " order by $orden";
}
de esta forma, en cada etiqueta pones el link con el orden correspondiente, pero recuerda que debes pasar la informacion necesaria para armar nuevamente la consulta, a que me refiero? si esta consulta es el resultado de un formulatrio (post), u otro link con datos pasados por get, debes suministrar esa misma informacion en el link, de modo tal que quede algo asi
Código:
<a href="script.php?...&orden=nombre">nombre</a>
donde ... son los parametros necesarios
saludos