Why is sort changing the order of lines with identical sort keys

Specify the sort keys separately with the criteria:

sort -k1,1nr -k2,2 inputfile

This specifies that the first key is sorted numerically in reverse order while the second is sorted as per the default sort order.

Quoting from POSIX sort:

-k keydef

The keydef argument is a restricted sort key field definition. The format of this definition is:

field_start[type][,field_end[type]]

where field_start and field_end define a key field restricted to a portion of the line (see the EXTENDED DESCRIPTION section), and type is a modifier from the list of characters 'b', 'd', 'f', 'i', 'n', 'r'. The 'b' modifier shall behave like the -b option, but shall apply only to the field_start or field_end to which it is attached. The other modifiers shall behave like the corresponding options, but shall apply only to the key field to which they are attached; they shall have this effect if specified with field_start, field_end, or both. If any modifier is attached to a field_start or to a field_end, no option shall apply to either. Implementations shall support at least nine occurrences of the -k option, which shall be significant in command line order. If no -k option is specified, a default sort key of the entire line shall be used.

When there are multiple key fields, later keys shall be compared only after all earlier keys compare equal. Except when the -u option is specified, lines that otherwise compare equal shall be ordered as if none of the options -d, -f, -i, -n, or -k were present (but with -r still in effect, if it was specified) and with all bytes in the lines significant to the comparison. The order in which lines that still compare equal are written is unspecified.

This would produce:

42 Life
17 Stackoverflow
12 Hi
9  LaTeX
9  Superuser
9  Ubuntu
7  C++
7  Hash

Looks like you can't rely on fields, so you'd need to rely on character column

         1         2         3         4         5         6         7         
1234567890123456789012345678901234567890123456789012345678901234567890123456789
stephane pts/0        :0               Fri Aug  1 09:48 - 14:34 (17+04:45)
stephane pts/13       :0               Fri Aug  1 16:27 - 13:51 (20+21:24)

From that:

last | sort -k1.44,1.46M -k1.48,1.49n -k51

Note that the M flag to sort on month names is not standard but available in several sort implementations including GNU sort (the one typically found on ArchLinux). Note that sort interprets the month names in the current locale, while last always outputs English month names, so you may want to run sort under LC_TIME=C if in a non-English locale.