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

If there are arrays as values they would be turned into hashes with numerical keys by the above and they would not be sorted.
For now it is left as an exercise how to also sort nested arrays.

Please note that the above code works for Puppet 6+.

For Puppet 5 you have to work around a bug and use the following code:

$temp = $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]

Hash($temp, 'hash_tree') # Hash() can produce a new Hash from a flattend tree
 .notice()               # output

For other poor souls that got here because they wanted to sort a hash by keys in Puppet like me: please check out puppetlabs/puppetlabs-stdlib#661 too.

The issue you ran into with convert_to seems to have been fixed in 2018. See the history of that function: https://github.com/puppetlabs/puppet/blob/main/lib/puppet/functions/convert_to.rb
The fix was released in Puppet 6.0 (https://tickets.puppetlabs.com/browse/PUP-8761).

Thanks @hlindberg! I have updated my comment accordingly.