What you need to do is the following:
1) Create a list of all of the attributes of your mysql table you would like to sort the table by.
2) Organize these into a switch statement at the top of your page in php, eg:
$sortby = intval($_GET['sort']);
$sqlExtra = "ORDER BY name ASC";
$sqlExtra = "ORDER BY name DESC";
//etc with the rest of the attributes
And then, after the switch statement append the $sqlExtra to your sql statement, eg:
$sql = "SELECT values FROM table ".$sqlExtra;
3) Now all you need is a bunch of links above or below or wherever relative to your table which must link back to this page but with a $_GET variable specified for 'sort', eg:
<a href="thispage.php?sort=1">Sort by name (A-Z)</a>
<a href="thispage.php?sort=2">Sort by name (Z-A)</a>
and for td u don`t wanna sort just add class="sorttable_nosort"
try using jquery for sortable table and pagination and use some ajax commands so your users don't have to refresh the page every time the user the sort functions the jquery can call up a external php file with the sql access to make it easier for your users