This is an example of how to recursively sort a Hash in the puppet language using the tree_each() function. Note that in versions before Puppet 6.0 the `convert_to` function does not accept the extra 'hash_tree' arg.ument.

sorthash.pp

# When you need to process a hash with keys in sorted order
# you may have found the `sort()` function - but it only
# operates on an Array.
#
# Most of the time what is wanted is simply achieved
# by taking the keys of a hash and sorting those and
# then iterating over the keys.
#
# When, however the wanted result is a new Hash
# with all keys sorted recursively then this becomes
# a bit of a headache to achieve with sorted
# key iteration.
#
# The solution is to use `tree_each()`.
#

# Here is some data as illustration. Note that nothing is in key order.
#
$data = {b => 2, c=> 3, a => 1, x => {b => 2, a=>1}}
$data.notice()

# The Hash is converted to flattened form - it skips all containers and only
# visits values in the tree. This is done as the inclusion of the containers would otherwise
# have preserved the order from the input.
#
$data.tree_each(include_containers=>false)    # flatten the tree
 .convert_to(Array)                           # convert the resulting iterator to an Array (since sort requires this)
 .sort                                        # sort the keys - they are the paths, i.e [a], [b], [c], [x,a], [x,b]
 .convert_to(Hash, 'hash_tree')               # Hash() can produce a new Hash from a flattend tree
 .notice()                                    # output

Thanks @hlindberg! I have updated my comment accordingly.