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

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.