Another approach might be to read chunks of your very large database, perhaps 100k to 500k records at a time, and sort each chunk into its own temporary file. Once you have read and sorted all of the data, do a sort/merge of the temporary files into a final sorted file. My gut feeling is that this would be more efficient than the "two at a time" approach you are taking.

Thinking about it further, read a chunk of your database then sort and print to two temporary files, one for letters, one for numbers. Then the sort/merge of the temporary files will be simpler keeping the two categories separate. Finally you can concatenate the letters and numbers merged files for your results file. In this code I am writing to in-memory scalars rather than disk files just to keep things tidy.

knoppix@Microknoppix:~$ perl -Mstrict -Mwarnings -E '
> my @values = qw{
>    041351920234
>    Rabbit
>    0343120
>    041271024500
>    0430870
>    Apple
>    041460301399
>    };
>  
> my $rsLets = do { \ my $lets };
> open my $letsFH, q{>}, $rsLets or die $!;
> my $rsNums = do { \ my $nums };
> open my $numsFH, q{>}, $rsNums or die $!;
> 
> say { $_->[ 1 ] ? $numsFH : $letsFH } $_->[ 0 ] for
>    sort {
>         ( $a->[ 1 ] <=> $b->[ 1 ] )
>         ||
>         (
>         $a->[ 1 ]
>         ? $a->[ 0 ] <=> $b->[ 0 ]
>         : $a->[ 0 ] cmp $b->[ 0 ]
>         )
>         }
>    map  { [ $_, m{^\d} ? 1 : 0 ] }
>    @values;
> 
> say ${ $rsLets }, q{-----------------};
> say ${ $rsNums }, q{-----------------};'
Apple
Rabbit
-----------------
0343120
0430870
041271024500
041351920234
041460301399
-----------------
knoppix@Microknoppix:~$
[download]

I hope this is of interest.