And here, for completeness, is a (presumably much slower) solution based on the opposite assumptions (extra letters last, and continue the comparison down the string). This is, of course, more or less equivalent to rewriting cmp with your own alphabet. It could undoubtedly be done faster with an iterative solution, but then it could also be done faster in C.

use strict;
use vars '$sortstr';
my @list = qw(a z b y c x); 
my @list2 = qw(zulu zuzu zucu charlie fred xray yankee bravo alpha); 

$sortstr = join('', @list);
my @sorted_list =  sort mycmp @list2; 

sub mycmp {
    my ($A, $B)= @_ ? @_ : ($a,$b);
    my $temp;
    my $Aspot = ($temp = index($sortstr,substr($A,0,1))) < 0 ? 
    length($sortstr) : $temp;
    my $Bspot = ($temp = index($sortstr,substr($B,0,1))) < 0 ? 
    length($sortstr) : $temp;
    
    return 
    $Aspot <=> $Bspot
        ||
        mycmp(substr($A,1),substr($B,1))
        ||
        $A cmp $B
}
[download]

Sorts to:
alpha zuzu zucu zulu bravo yankee charlie xray fred