Update: Added undef's to the list to imitate the OP's request regarding undef's. After sorting, move any undef's from the start of the list to the end.

The following is a fun exercise if wanting to simulate work inside the foo function.

Thank you, Randal L. Schwartz for the Schwartzian transform technique.

use strict;
use warnings;

# http://www.perlmonks.org/?node_id=1192544

use List::Util 'shuffle';
use Time::HiRes 'time';

sub foo { sleep 0; $_[0] }

srand 0;

my @unsorted = shuffle ( 'aaaa'..'zzzz', (undef) x 7 );

printf "Number of elements to sort    : %d\n",
  scalar @unsorted;

{
  no warnings 'uninitialized';

  my $start  = time;
  my @sorted = sort { foo($a) cmp foo($b) } @unsorted;

  # move any undef's from the start of the list to the end
  my $i = 0; $i++ until ( defined $sorted[$i] );
  push @sorted, splice(@sorted, 0, $i) if $i;

  printf "Without Schwartzian transform : %6.3f seconds\n",
    time - $start;
}

{
  no warnings 'uninitialized';

  my $start  = time;
  my @sorted = map  { $_->[0] }
               sort { $a->[1] cmp $b->[1] }
               map  { [ $_, foo($_) ] } @unsorted;

  # move any undef's from the start of the list to the end
  my $i = 0; $i++ until ( defined $sorted[$i] );
  push @sorted, splice(@sorted, 0, $i) if $i;

  printf "With ++ Schwartzian transform : %6.3f seconds\n",
    time - $start;
}

__END__

Number of elements to sort    : 456983
Without Schwartzian transform : 24.939 seconds
With ++ Schwartzian transform :  2.832 seconds
[download]

Perl is fun. I'm always learning and had no idea the speed gain possible with the Schwartzian transform until now. I also tried without sleep 0 inside foo to better understand the overhead imposed by method calling. The Schwartzian transform is still faster. Wow!

sub foo { $_[0] }

Number of elements to sort    : 456983
Without Schwartzian transform :  4.680 seconds
With ++ Schwartzian transform :  2.053 seconds
[download]

Regards, Mario