Yes, you should show them the data from the top (page 1).
Assuming the user has looked at all rows up to say page 3. They couldn't find what they were looking for and decided to re-sort. There's no way to know in the new sort order as to whether data in the first 2 pages have been reviewed.
In fact, because you changed the sort order, the assumption is that the sort you picked would have been the most relevant and thus the data you want ought to be at the top.
Since the page will effectively need to be refreshed anyways to resort the data, from the user's perspective, staying "on the same page" doesn't really mean much.