Here is tricky scenario that I just thought of…
Let’s say you are reading your PM’s.
You have 93 Messages, with 10 Messages shown per page (i.e. 10 pages).
Currently, you are have PM’s sorted By Date, in Descending Order, and you are done reading all of the newer PM’s and way back on Page #7 (i.e. Messages 70-79).
In the UI Navigation, you see this…
|< < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 > >|
You spot a PM from your long-lost lover, and impulsively decide to “Sort by Sender” to see if you have any more old steamy PM’s left from your lover… (Bittersweet, we know! But who could resist?!) 
Anyways…
In this contrived scenario, when you click to “Sort by Sender” (in Ascending Order)…
1.) What Page do you end up on??
Do you remain on Page #7 ??
Do you go back to Page #1 since things have been re-sorted??
2.) If you stay on Page #7, then…
What happens to the PM range you were viewing??
Does the website have to “Sort by Sender (in Ascending Order)”, and then figure out where the new Page #7 would be, and then take you back to this New Page #7 ??
3.) Does some other behavior happen??
Pretty confusing topic if you think about… :-/
I thought I was making good progress on programming my first-ever Pagination Module when all of these questions popped into my head?! 
Your answers to my questions above will have a significant impact on how I write my PHP and tweak my SQL!!
Sincerely,
Debbie