One approach is to say that any sort routine should never need an additional value to be passed in. Any case which looks like it needs that can have the assumption solved by prebinding an argument with a closure.

my $real_sort_routine = sub {$sort_routing->(\%href)};
foreach (sort $real_sort_routine keys %{ $somehashref }) {
  #do stff
}
[download]

Now that you've moved the binding elsewhere, you can choose to put the binding wherever it makes sense - possibly during building up the definitions of sorts that you need.

You can find an example of setting up a complex sort using closures at Re: Fun with complex sorting on arbitrary criteria list..

A useful trick to know: if you'll be building a sort function in a different package than you're calling sort in, you'll want your functions to all have a prototype of ($$). With 5.6 or better, that will cause Perl to pass $a and $b in rather than setting appropriate globals in the package that sort was called from. (Which might not be the package that the sort function looks in - very confusing if it happens to you.)