Comment by aibara

If the view is set to "by last visited," Firefox's history searches are sorted by last visit. Maybe you had some add-on that changed the behavior.