I assume that you're using getResources or pdoResources for the search. The trouble is that they don't know what's in the URL. You need a custom snippet to get the query parameter from the URL:
In the getResources tag:
Then a custom snippet:
/*GetSortBy snippet */
return $_GET['sortby'];
Also, your tags above are incorrect (you can tell by looking at the URL, which should have ? &sortby=`ASC` at the end). The parameter goes inside the link tag with no question mark:
<li><a href="[[~[[*id]] &sortby=`ASC`]]">Newest</a></li>
I always have to look at my own book to get this right.
You could also use placeholders and a little more code in the snippet so the user would see something like:
Sorted By Newest --
Sort by Oldest
or
Sorted by Oldest --
Sort by Newest