I tried that, and I think it might work, but it takes an extraordinary amount of time. So much so that I never actually saw it complete. To counter that, I tried extracting and deleting the keys in batches of 1000:

my @ordered;
while( my $n = keys %hash ) {
    my @temp;
    for ( 1 ..  $n < 1000 ? $n : 1000 ) {
        push @temp, scalar each %hash;
    }
    delete @hash{ @temp };
    push @ordered, @temp;
}
[download]

But it still takes an extraordinary amount of time.

Update: The above has a precedence problem with the ternary expression! And results in for loop operating from 1 to 1.

Add a set of parens and things go much more quickly:

my @ordered;
while( my $n = keys %hash ) {
    my @temp;
    for ( 1 ..  ( $n < 1000 ? $n : 1000 ) ) {
        push @temp, scalar each %hash;
    }
    delete @hash{ @temp };
    push @ordered, @temp;
}
[download]

BTW: If I ever manage to get the keys out of the hash and into an array without blowing memory, then I intend to use your Sort::Key to sort them in-place. But, there doesn't seem to be a an in-place version of keysort that doesn't take a callback?

I can use keysort_inplace{ $_ } @ordered;, but doesn't the callback slow things down?

I can use rsort_inplace @array and just assign the numbers reversed, but it seems there should be a sort_inplace() version?