I did sort and pagination functions by using MySQL, Oracle, Sybase in various projects, here summary the usage of PHP/MySQL's sort/pagination which combine MySQL's 'limit' plus PHP's superglobal SESSION.

PHP's $_SESSION[] and MySQL's limit are very useful in Ajax-style pagination and sort refreshing.
To apply $_SESSION[], just start session at the very beginning of the codes:
$start_session();

Then consider to put the following in $_SESSION:
$_SESSION['query_sql']: current query string.
$_SESSION['total_records']: total records of the query, so don't need to select count(*) every time.
Even super, you can put dynamic variables such as current_page, sort_by column into $_SESSION.

After assembly that, let's list the steps:

A. sort:

<a href="javascript:void(0);" onClick="sort_data(event, '<?=$div;?>','NAME')">
<img src="images/up.gif" border="0" width="12" height="12" alt="up"></a>
<a href="javascript:void(0);" onClick="sort_data(event, '<?=$div;?>','NAME DESC')">
<img src="images/down.gif" border="0" width="12" height="12" alt="down"></a> 

(2) JavaScript:
in a prototype OO environment(inside a class), the sort_data should like this:

sort_data: function(e, div, sortby) {
    if (sortby) {
        this.url += '&sort='+sortby;
    }
    new Ajax.Updater(div, this.url, {
        method: 'get',
        evalScripts: true,
        onLoading: function() {
            // when searching, a searching icon displayed instead of sort icon.
            if(!(Prototype.Browser.IE)) {
                var t = e.element();
                $(t).replace('<img src="images/processing.gif"
                    width="12" height="12" border="0"/>');
            }
        }
    });
},

(3) PHP: in the control php script:

if (isset($_GET['sort'])) {
		$query = $_SESSION['query_sql'];
    $new_order = $_GET['sort'];
    if (eregi("order by", $query)) {
        $query = preg_replace("/order by.*$/i", " order by " . $new_order, $query);
    }
    else {
        $query .= " order by " . $new_order;
    }
    $_SESSION['query_sql'] = $query;
}

B. pagination

printf("<a href='javascript:void(0);' onClick="page_data(event,'$url=%d','%s')">
    [Prev]</a>n", ($current_page-1), $div);
printf("<a href='javascript:void(0);' onClick="page_data(event,'$url=%d','%s')">
    [Next]</a>n", ($current_page+1), $div);
      

page_data: function(e, div) {
    if (!$(div).visible()) $(div).show();
    new Ajax.Updater(div, this.url, {
        method: 'get',
        evalScripts: true,
  onLoading: function() {
      if(!(Prototype.Browser.IE)) {
          var t = e.element();
          $(t).replace('<img src="images/processing.gif" width="12"
             height="12" border="0"/>');
      }
  }
    });
},

if (isset($_GET['page'])) {
	$query = $_SESSION['query_sql'];
	...
	if (preg_match("/limit /i", $query)) {
		$query = preg_replace("/limit.*$/i",
            " limit $row_no, ".ROWS_PER_PAGE, $query);
	}
	else {
		$query .=  " limit  $row_no, ".ROWS_PER_PAGE;
	}
	$_SESSION['query_sql'] = $query;
}