I also had this problem this morning on Moodle 3.0.3+. I looked at the source code and the sort features are hidden if the number of courses in the category, does not match the number of courses the user can see in the category.
I figured somehow the course count was out of sync. So i added a course and all the sort features came back . I then removed the course and I still had all the sort features.
I have no idea how to reproduce this or how it happened or of its a problem in later Moodle versions. So I have not filed a tracker issue. I hope this helps someone though.