which server version are you running?

Adding first_name as an additional key would also help speed up these queries.

edit: removed PK suggestion - it was at end of sql.

Version 10.1.16 but id had this problme on mysql 5.6 too
I fixed it with second order sort condition. Also It will fix with index on first_name.
But i think default behavior it isn't correct
I get backup with phpmyadmin, i don't know why PK is at end of sql.
Separate table structure and data added
employee_structure.zip

You are ordering the result set by a non-unique column. You can only expect that if first_name_1 < first_name_2, then all rows with first_name_1 will come earlier (in case of ASC) or later (in case of DESC) than all rows with first_name_2. There is nothing that guarantees any specific order inside a group with the same first_name. Technically, you can even get different results running the same query, e.g. one with LIMIT 20 OFFSET 0, although in practice it rarely happens; and of course, the second query knows nothing about the previous query.

If your next argument is "it used to work on 5.5" – yes, it might well be true, but it worked by pure luck, the behavior has never been defined and guaranteed.

See also https://bugs.mysql.com/bug.php?id=69732 for longer discussion.