The boys in the back garden
Here's a story to illustrates the problem with tables and pagination:
"Good morning Mr. Smith! Here, per your request, 20 of the town's finest - 10 young men and 10 young women".
"It is ever so kind of you Gordon. Now I'd like to start by having a look at the girls, please send the boys somewhere".
"Very well Sir. BOYS! chop, chop! Off you go to the back Garden please. Quick, quick... we haven't got the whole day... There you are Mr. Smith, the girls only."
"Marvellous my dear Gordon. Now which one of the bunch is the tallest?"
"Oh Mr. Smith, clearly the leftmost girl is the tallest."
"Oh, yes, yes Gordon... clearly she is, that I can see for myself. But I mean from the whole group - girls AND boys."
"I see Mr Smith, in this case, allow me to call the boys backs!"
Data and tables
- Data in tables is ordinal - even if not sorted.
- Consider a vertical scroll - no pages.
- Pages are organisational artefacts which date back to codices. But the pages segment what would be an ordinal list on a scroll.
- If the list is now sorted again, what point is there for the old page to exist?
Consider that yellow pages tomorrow changes from alphabetical sorting to chronological one (year established), what value anyone gets from knowing something was on page 62 in the old version?
Not only for sorting
Anything that changes the data, namely filters (like pages) and sorting, should be regarded as if it has yielded a new dataset (or subset). There are many issues that can arise from this - like when the users searches for items starting with 'C' and then add and item starting with 'B'.
It is worth considering which of these filters and sorts cannot work together and when they must be disabled (nearly always when adding a new record).
The general chain is like so:

Any partial that changes invalidates all those after it.
So in your case, a sort renders the pagination invalid, since the content of page X is no longer the same content.