Now try it on a file with a million lines...

Update: Apparently, this is seen as sarcasm or otherwise unhelpful; so here are some statistics:

Using Tie:File and an inplace Fischer-Yates shuffle to sort various sized files:

1. 100 lines: 58 milliseconds.
2. 1,000 lines: 2 seconds
3. 10,000 lines: 194 seconds
4. 100,000 lines: after 3 1/2 hours of cpu I got sick of listening to the fan thrashing itself to death trying to keep the cpu cool, and aborted.
5. 20, 000,000 (the OP's task): Probably best measured in half-lives of Plutonium.

The test code should anyone wish to verify my figures.

#! perl -slw
use strict;
use Tie::File;
use Benchmark::Timer;

our $N ||= 1000;

sub shuffle {
        my $ref = @_ == 1 ? $_[ 0 ] : [ @_ ];
        for( 0 .. $#$ref ) {
                my $p = $_ + rand( @{ $ref } - $_ );
                @{ $ref }[ $_, $p ] = @{ $ref }[ $p, $_ ];
        }
        return unless defined wantarray;
        return wantarray ? @{ $ref } : $ref;
}

open OUT, '>', 'junk.dat' or die $!;
printf OUT "%030d\n", $_ for 0 .. $N;
close OUT;

my @lines;
tie @lines, 'Tie::File', 'junk.dat';

my $T = new Benchmark::Timer;
$T->start( "shuffle $N" );

shuffle \@lines;

$T->stop( "shuffle $N" );
$T->report;
[download]