1) The one that will always work is to split up the file in smaller chunks, sort the separately, and then merge them again.

2) If you work on a unixish system, you could try to abuse you system's sort program, at least GNU sort handles memory limitations automatically by creating temporary files.

3) Search on CPAN. Maybe there's a module that does what you want? File::Sort looks promising at a first glance (actually CPAN should be your first place to look ;-)

3) Search on CPAN. Maybe there's a module that does what you want?

Sort::External

Y'know, Sort::External is designed for exactly what the original poster wants to do... but few people seem to find it on CPAN.

Sort::External was my first CPAN distro, and the people on the modules mailing list prevailed upon me to release it it under the academically correct name. I occasionally regret having taken that advice.

FWIW, here's the definition of "external sort" from nist.gov:

Any sort algorithm that uses external memory, such as tape or disk, during the sort. Since most common sort algorithms assume high-speed random access to all intermediate memory, they are unsuitable if the values to be sorted don't fit in main memory.

--
Marvin Humphrey
Rectangular Research ― http://www.rectangular.com

  @lines = <INPUTFILE>;
  @lines =  sort { (split($a, /\t/))[2] <=> (split($b, /\t/))[2] } @li
+nes;
[download]

I believe the most recent Perls have a special in-place sort() optimization when you're sorting an array and assigning it back to itself. (UPDATE: Yup, it was added in v5.8.4)

-sam

Or you could try something twice as fast that uses much less memory. In this case I'd likely sort parallel arrays (though it isn't too complicated to do something even faster that uses even less memory, such as fast, flexible, stable sort).

my @size= map { ( split /\t/, $_ )[2] } @in;
my @idx= sort { $size[$a] <=> $size[$b] }, 0..$#in;
@in= @in[@idx];
[download]

And I'd check how much paging space is configured. It sounds like that could be increased.

- tye        

I really doubt that's going to work in 1GB of RAM on a 400MB input (and don't worry about paging space - if you start paging then any speedup you gained just went bye-bye). I guess it's possible, but this line looks pretty bad to me:

   @in = @in[@idx];

Or do you happen to know that Perl does that in-place on @in? I guess the only way to really know would be to try it, but unfortunately I do have some real work to do...

-sam

#!/usr/bin/perl
use strict;
use warnings;

my %data;
my $file = $ARGV[0] or die "Usage: $0 <input_file>";
open(my $fh, '<', $file) or die "Unable to open '$file' for reading: $
+!";

my $pos = tell $fh;
while (<$fh>) {
    my $size = (split /\t/)[2];
    $data{$size} = exists $data{$size}
              ? $data{$size} . ":$pos"
              : $pos;
    $pos = tell $fh;
}
for my $size (sort {$b <=> $a} keys %date) {
    for my $pos (split /:/, $data{$size}) {
        seek($fh, $pos, 0);
        my $line = <$fh>;
        print $line;
    }
}
[download]

Note: This code is untested an is not optimal. It was just an idea I had that you might want to try. It will output lines of files with the same size in the same order they appeared in the original file.

400MB is not a “very large” file. It is “not a very large file at all.”

What you need to do is use a disk-based sort. There are many of these in CPAN, such as File::Sort. Or, how aboutSort::External? As it happens, “sorting” is one of the most extensively-studied and extensively-implemented algorithms in all of computer science. (The other is “searching,” saith the august Dr. Knuth.) My CPAN-search found 1,929 choices under “Sort.”

Although virtual-memory sorting is simple and easy to conceptualize, it is not intended for large volumes of data. You're seeing it choke, and fail, trying to do a task that is much larger than it was designed for.

Disk-oriented tools, of which there are a great many available, will automatically handle the job by splitting the total job into a group of disk-based spill files, then merging those files together for you. An arbitrary amount of data can be sorted in this way and it will be quite fast.

(Heck, you can even sort data using nothing more than magnetic tape! When all those campy old sci-fi movies needed to film “a computer,” the operators would obligingly start a tape-sort.)

> # The file is tab delimited (your time field having spaces shouldn't
+ matter)
> cat tmp.txt
3       1a      2       b
2       2c      3       b
1       3b      1       b
> # The char between the quotes is a tab ("\t" works in ksh)
> sort -t" " -k3n tmp.txt
1       3b      1       b
3       1a      2       b
2       2c      3       b
>
[download]

system('sort',"-t", "\t","-k3n","tmp.txt");
[download]