Sort Order not working on second page

Sort Order not working on second page

We have 200+ potentials in the database. When we look at the all potentials view and sort by stage the items on the first page are sorted correctly. When we go to the second page of the view, the items seem to be resorted in some random manner.  How do we keep this from happening on the 2nd and subsequent pages?