> Does `sorted` break ties deterministically?

Yes, indeed
http://wiki.python.org/moin/HowTo/Sorting#Sort_Stability_and_Complex_Sorts