I'd go with the sort id, with the column headers as links back to the sorted page.
Before I got too into DOM I put togeather the AJAX method, some of my users didn't see the "loading" message, and on longer sorts they would spam the column or assume it was broken. In this case I liked the page refresh because they were assured it was working. Other then that I liked it more.
That said, I've moved to using javascript for this, much cleaner and offloads onto the client.