[BeeOnRope]

Well SHA256 is a red herring here: one could suggest any suitable fast hash, non-crytopgraphic hash instead.

Yes, it takes time linear in the length of the thing you are sorting, but comparison sort is generally worse in that respect: comparison also takes up to linear time in the comprands, and you have to compare each element not just once but log n times [1].

So the time to hash all the elements once (if the hash is not already cached in the element) is going to be a small part of the sort time.

[1] There are ways around repeatedly re-comparing the entire key, but they work mostly in specialized cases.