Постраничная навигация с сортировкой

У меня таблица с сортировкой и если сортировать столбец ID то на первой странице она происходит, но если перейти на вторую то сортировка сбрасывается. То есть у меня 52 ID я нажимаю сортировать по убыванию и на первой странице 52 51 50 49 48, когда переключаю на вторую 6 7 8 9 10

         <?php 
 $key_array = array('id', 'date', 'surname', 'name', 'patronymic', 'text');
$sort_array = array('asc', 'desc');
$theads = array(
    'id' => array('name' => 'ID', 'cols' => '1'),
    'date' => array('name' => 'Дата рождения', 'cols' => '2'),
    'surname' => array('name' => 'Фамилия', 'cols' => '2'),
    'name' => array('name' => 'Имя', 'cols' => '2'),
    'patronymic' => array('name' => 'Отчество', 'cols' => '2'),
    'text' => array('name' => 'Биография', 'cols' => '2'),
);
if (isset($_GET['key'])) {
    $key = $_GET['key'];
    $sort = $_GET['sort'];
} else {
    $key = 'id';
    $sort = 'asc';
}
if(in_array($key, $key_array) && in_array($sort, $sort_array))
{
    $num = 5;
$page = $_GET['page'];
$result00 = mysql_query("SELECT COUNT(*) FROM message");
$temp = mysql_fetch_array($result00);
$posts = $temp[0];
$total = (($posts - 1) / $num) + 1;
$total =  intval($total);
$page = intval($page);
if(empty($page) or $page < 0) $page = 1;
if($page > $total) $page = $total;
$start = $page * $num - $num;   
     $query = "SELECT id,DATE_FORMAT(`date`,'%d.%m.%Y') as `date`,surname,name,patronymic,text FROM message ORDER BY $key $sort LIMIT $start, $num";
    $result = mysql_query($query);
}
else exit("неверный формат запроса!");
print "<table class='table table_sort'>";
print "<thead>";
foreach ($theads as $k => $thead) {
    if ($k === $key) {
        $img = "<img src='$sort.png' style='width:18px;'>";
        $soort = ($sort == 'desc' ? 'asc' : 'desc');
    } else {
        $img = '';
        $soort = 'asc';
    }
    $get = http_build_query(array(
        'key' => $k,
        'sort' => $soort
    ));
    print "<th class='col-md-{$thead['cols']} tbl_tlt'><a href=\"?$get\">{$thead['name']}</a>$img</th>";
}
print "</thead>";
print "<tbody>";
// Отформатировать и вывести каждую строку таблицы
while ($row = mysql_fetch_array($result))
{
    print "<tr>";
    print '<td>'.$row['id'].'</td><td>'.$row['date'].'</td><td>'.$row['surname'].'</td><td>'.$row['name'].'</td><td>'.$row['patronymic'].'</td><td>'.$row['text'].'</td>';
    print "</tr>";
}
print "<tbody>";
// Завершить таблицу
print "</table>";
   ?>
<?
// Проверяем нужны ли стрелки вперед
// Находим две ближайшие станицы с обоих краев, если они есть
if($page - 5 > 0) $page5left = ' <li><a href="index.php?page='. ($page - 5) .'&sort=$sort">'. ($page - 5) .'</a></li> ';
if($page - 4 > 0) $page4left = ' <li><a href="index.php?page='. ($page - 4) .'&sort=$sort">'. ($page - 4) .'</a></li> ';
if($page - 3 > 0) $page3left = ' <li><a href="index.php?page='. ($page - 3) .'&sort=$sort">'. ($page - 3) .'</a></li> ';
if($page - 2 > 0) $page2left = ' <li><a href="index.php?page='. ($page - 2) .'&sort=$sort">'. ($page - 2) .'</a></li> ';
if($page - 1 > 0) $page1left = '<li><a href="index.php?page='. ($page - 1) .'&sort=$sort">'. ($page - 1) .'</a></li> ';
if($page + 5 <= $total) $page5right = ' <li><a href="index.php?page='. ($page + 5) .'&sort=$sort">'. ($page + 5) .'</a></li>';
if($page + 4 <= $total) $page4right = ' <li><a href="index.php?page='. ($page + 4) .'&sort=$sort">'. ($page + 4) .'</a></li>';
if($page + 3 <= $total) $page3right = ' <li><a href="index.php?page='. ($page + 3) .'&sort=$sort">'. ($page + 3) .'</a></li>';
if($page + 2 <= $total) $page2right = '<li><a href="index.php?page='. ($page + 2) .'&sort=$sort">'. ($page + 2) .'</a></li>';
if($page + 1 <= $total) $page1right = ' <li><a href="index.php?page='. ($page + 1) .'&sort=$sort">'. ($page + 1) .'</a></li>';
// Вывод меню если страниц больше одной
if ($total > 1)
{
echo "<div class=\"pagination\">";
echo $pervpage.$page5left.$page4left.$page3left.$page2left.$page1left.'<li class="active"><a>'.$page.'</a></li>'.$page1right.$page2right.$page3right.$page4right.$page5right.$nextpage;
echo "</div>";
}
?>