Any solution is going to be expensive.

1. Don't eat memory:

   my $ignore = '(^The )|(^A )';
   ...
   @sorted = sort { 
       $a =~ s/$ignore//;
       $b =~ s/$ignore//;
       lc( $a ) cmp lc( $b );
     } @indata;
   [download]

2. Or store better keys first:

   %data = map { my $data = $_; s/$ignore//; ($_, $data } @indata;
   
   @sorted = @data{ sort{ lc( $a) cmp lc( $b)} keys %data };
   [download]

Hope this helps,

Jeroen
"We are not alone"(FZ)