Are you passing a url parameter to do the sort? It is probably keeping it in the url and causing the sort to turn on and off, or switch order. You can tell the recordset to not include the url parameter in the navigation links with code like:
<?php
$Recordset1->RemoveParams[] = "sort";
?>
Just add it below the recordset making sure to use your recordset name and the url parameter you want to be removed from the navigation links.