Gondolom már nem aktuális, de jól esett kitalálni a megoldást:

#!/usr/bin/perl

use strict;

my @input = (
'1.+Béla',
'Örök+Eutanázia+Roberta',
'Kiss+Miska+András',
'Aaa+Aaa',
);

sub def_k {
shift =~ m/\+([^+]+)/;
return $1 || "";
}

my @output =
#map { $_->{'o'}}
sort { $a->{'k'} cmp $b->{'k'} }
map +{ 'o'=>$_, 'k'=> def_k($_) }, @input;

foreach my $o (@output) {
#print join( "\n", @output );
print $o->{'k'}.' -- '.$o->{'o'}."\n";
}

Az alkalmazott ötlet a http://en.wikipedia.org/wiki/Schwartzian_transform. A két kommentelt sor a teszteléshez van, élesben az első map veszi ki az eredeti stringeket a hashekből.
Remélem valakinek még hasznos lesz!
Üdv: Mijo