in reply to In-place sort with order assignment

I believe @a = sort @a; works in place. O(1N) memory, O(NN log N) time. 

my @keys;
keys(%hash);  # Reset iterator
#while (my $k = each(%hash)) {  # if 0 or '' are possible keys
while (my $k = each(%hash)) {
   push @keys, $k;
}

@keys = sort @keys;
for (0..$#keys) {
   $hash{$keys[$_]} = $_;
}

[download]

Replies are listed 'Best First'.
Re^2: In-place sort with order assignment
by BrowserUk (Patriarch) on Sep 20, 2010 at 14:00 UTC
    I believe @a = sort @a; works in place. O(1) memory, O(N) time.

    That isn't the (whole) problem. Creating the array from the keys of the hash effectively doubles memory usage, before you ever get to the sort.

    This has already been discussed in the thread.

    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.
[reply]
      Seems to me the very complex solutions presented use at least that much memory too, so consider it a simplification.
[reply]

        Not so complex, and not so memory hungry (+20%): 

        #! perl -slw
use strict;
use sort qw[_quicksort];
use Time::HiRes qw[ time ];
use Data::Dump qw[ pp ];

our $N //= 1e6;
our $M //= int $N / 10;

my $val = 'AAAAA';
my %words;
undef $words{ $val++ } for 1 .. $N;

<STDIN>;

my $start = time;
my @ordered;
my @temp; $#temp = $M;
while( my $n = keys %words ) {
    my $m = $n < $M ? $n-1 : $M-1;
    $#temp = $m;
    $temp[ $_ ] = scalar each %words for 0 .. $m;
    delete @words{ @temp };
    push @ordered, @temp;
}

@ordered = sort @ordered;

my $elapsed = time - $start;
printf "Took %.6f seconds for $N items (%.6f per item)\n",
    $elapsed, $elapsed / $N;

<STDIN>;
__END__
C:\test>junk38 -N=10e6 -M=10e3
1.5gb
Took 113.162400 seconds for 10e6 items (0.000011 per item)
1.8gb

        [download]
        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.
[reply]
[d/l]

In Section Seekers of Perl Wisdom