I am confident that, in addition to my hash, I can have two additional arrays with 1000 items each. On the first pass through the hash using each, you check to see if the current key in the hash is lt than the first element in the array. If yes, you unshift, if not you check the next item until you find the proper location and use splice. If you reach the end of the array and it is less than 1000, you push. At the end, you check if you have 1001 items and you pop. At the end of the first pass, you now know the first 1000 items. You begin your second pass. This time, when you encounter an item in your first array, you assign its appropriate value while simultaneously populating the 2nd array (using the last element of the first).

Now of course this is silly - there are much better data structures than an array but I hope you get the idea.

I guess I'm being thick here but, at the end of your second pass, you have 2000 items in 2 arrays, and the original number in the hash. Then what?

And, does each "pass" mean a pass over 1000 (or 2000) elements of the array(s)? Or a full (millions) pass over the keys of the hash?

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

BrowserUk,
Ok, I must be the one being thick here so I will give you a real solution as soon as I finish lunch.

Update:

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

my %hash = map {$_ => undef} 'a' .. 'z';
my ($at_once, $cnt, @bot_n, %known) = (3, 0, (), ());

while (1) {
    while (my ($key, $val) = each %hash) {
        next if defined $val;
        if (exists $known{$key}) {
            $hash{$key} = $known{$key};
            next;
        }
        my $inserted;
        for (0 .. $#bot_n) {
            if ($key lt $bot_n[$_]) {
                splice @bot_n, $_, 0, $key;
                $inserted = 1;
                last;
            }
        }
        push @bot_n, $key if ! $inserted;
        pop @bot_n if @bot_n > $at_once;
    }
    last if ! @bot_n;
    %known = ();
    for (@bot_n) {
        $known{$_} = ++$cnt;
    }
    @bot_n = ();
}
use Data::Dumper;
print Dumper(\%hash);
[download]

As you can see, this works but could be greatly improved with a data structure other than an array to maintain order. I converted the 2nd array to a hash to avoid doing a binary search since American football is about to come on and Sunday is family day :-)

Update 2: This requires N / M passes through the hash where N represents the total number of keys and M represents the maximum number of items to sort at once. Using an array and a hash to keep track of the current unknown bottom N is extremely inefficient (from runtime perspective) but data structures that support a faster run time also consume more memory. Finding a balance of speed and memory is left as an exercise for the reader :-)

Cheers - L~R