Hierbij mijn oplossing
#! /usr/bin/perl
use strict;
use constant RANGESIZE => 10;
use constant DEBUGPRINT => 0;
# argumenten: N filenaam
# de file bevat unieke getallen in de range 0..N
# geef de missende getallen met zo weinig mogelijk geheugengebruik
# (niet inlezen, geen bitmap maken)
# en zonder de file te sorteren met een externe sort
my $N=shift;
my $file=shift;
our $TempFileSeqNbr=0;
OnderzoekFile($file,0,$N);
print STDERR "$TempFileSeqNbr tijdelijke files gemaakt\n" if DEBUGPRINT;
sub OnderzoekFile
{
my $file=shift;
my $lower=shift;
my $upper=shift;
print "$file $lower $upper\n" if DEBUGPRINT;
if ($upper+1-$lower <= RANGESIZE) {
LeesHeleFile($file,$lower,$upper);
return;
}
my $pivot=int(($lower+$upper) / 2);
my $lcnt=0;
my $hcnt=0;
my $lfile=GeefTempFile();
my $hfile=GeefTempFile();
# open de inputfile
open(INPUT,"<$file"

or die "Open error on $file\n";
# open de outputfiles
open(LOW ,">$lfile"

or die "Open error on $lfile for output\n";
open(HIGH,">$hfile"

or die "Open error on $hfile for output\n";
while(<INPUT>

{
chomp();
my $nbr=$_;
if ($nbr <= $pivot) {
print LOW "$nbr\n";
$lcnt++;
} else {
print HIGH "$nbr\n";
$hcnt++;
}
}
close INPUT;
close LOW;
close HIGH;
print "$lfile=$lcnt $hfile=$hcnt\n" if DEBUGPRINT;
OnderzoekFileEnDelete($lfile,$lcnt,$lower,$pivot);
OnderzoekFileEnDelete($hfile,$hcnt,$pivot+1,$upper);
}
sub OnderzoekFileEnDelete
{
my ($file,$cnt,$lower,$upper)=@_;
unless ($upper - $lower + 1 == $cnt) {
OnderzoekFile($file,$lower,$upper)
} else {
print "Onderzoek $file ($lower - $upper - $cnt) onnodig\n" if DEBUGPRINT;
}
unlink $file;
}
sub LeesHeleFile
{
my ($file,$lower,$upper)=@_;
my @nbr=((0) x ($upper-$lower+1));
open(INPUT,"<$file"

or die "Open error on $file\n";
while(<INPUT>

{
chomp();
my $nbr=$_;
die "$nbr klopt niet met range $lower .. $upper in file $file\n"
if $nbr < $lower || $nbr > $upper;
$nbr[$nbr-$lower]=1;
}
close INPUT;
for my $i (0..$#nbr) {
printf ">>> %d\n",$i+$lower
unless $nbr[$i];
}
}
sub GeefTempFile
{
$TempFileSeqNbr++;
return sprintf("ch0201-%04d.tmp",$TempFileSeqNbr);
}
De bijbehorende output is
>>> 0
>>> 35669
>>> 108293
>>> 126816
>>> 235522
>>> 266142
>>> 296793
>>> 395810
>>> 429365
>>> 522180
>>> 526613
>>> 540421
>>> 547737
>>> 551175
>>> 601002
>>> 633031
>>> 667441
>>> 731248
>>> 785671
>>> 804030
Door DEBUGPRINT op 1 te zetten krijg je allerlei extra informatie