En tu enlace haz de pasar un valor para actuar de una ú otra forma... ejemplo:
Código PHP:
<a href="mismapag.php?orden=ascendente">a-z</a> <a href="mismapag.php?orden=descendente">z-a</a>
Entonces...
Código PHP:
<?php
if($_GET['orden']=="ascendente") $query= "SELECT * FROM tabla ORDER BY campo ASC";
else if($_GET['orden']=="descendente") $query= "SELECT * FROM tabla ORDER BY campo DESC";
// demás cosas
$consulta= mysql_query($query);
// etc...
?>

en realidad se puede simplificar mucho y abrá que hacer validaciones ($_GET puede no existir) .. pero es más ilustrativo así.