$ perl -pe '$_ = rand(100000000). " $_"' bigfile \
    | sort -k 1n | perl -pe 's/^\d+ //' > bigfile_sorted

##</code><code>##

perl -ne 'BEGIN { for (1..16) { open my $fh, ">tmp$_"; push @f, $fh" }
    print { $f[rand16]} $_' bigfile

(randomise the files tmp1 .. tmp16), then

$ cat tmp* > bigfile_sorted
$ rm tmp*