Instead of pumping methods into hash, what about a module `HashTSorter` with `def self.each_key_sorted(hash)` and `def self.sort_each_child(hash, node, &block)`?

Could be monkeypatching core classes is Just What You Do and I'm not fully on the Rubytrain yet :)  If that's the case, I will stop worrying and learn to love the monkeypatch.