The <=> can dig into objects and hashes, so you can use something like $a->key->{'other'} <=> $b->key->{'other'}. Proof of concept:

#/usr/bin/perl
use warnings;
use strict;
use Data::Debug;

my @things;
push @things, Thing->new() for (1..10);
debug @things;
my @sorted = sort { $a->key->{'other'} <=> $b->key->{'other'} } @thing
+s;
debug @sorted;

package Thing;
sub new { return bless { key => { other => int(rand(42))} }, 'Thing'; 
+}
sub key { return shift->{'key'}; }
1;
[download]

I hope that is helpful :)