Is there a name for that kind?

Question

What is the name of the sort used in this answer ? I googled for a "perfect insertion sort" but didn't find anything. Here is the code from this answer:

#this is O(n) instead of O(n log n) or worse
sub perfect_insert_sort {
    my $h = shift;
    my @k;
    for my $k (keys %$h) {
        $k[$h->{$k}{order}] = $k;
    }
    return @k;
}

Answer 1

I think I should probably be called perfect_bucket_sortinstead perfect_insertion_sort.

Answer 2

This is not an insertion sort, in fact it is not even a sort, because the theoretical lower bound for them is O (nlogn).

So this is probably a bucket sort; also note that no comparisons have been made :)

Answer 3

. , , map . , :

my $hash = {
   foo => { order => 3 },
   bar => { order => 20 },
   baz => { order => 66 }, 
};

"" . , $perfect_insert_sort, 67 ( 3, 20 66), undef .

. - , , .

@downvoter:

, , . . - .

:

• ( )
• An output is a rearrangement or reordering of input.

Part 2, of course, is being implemented: the hash structure is being converted to a list. However, part 1 is not fulfilled. The determination of the order does not occur. When pasting, the order was predefined. If it were a sort, then there would also be the following:

my @data = ... ;
my $index = -1;
my %stored = map { ++$index; $_ => { order => $index } } @data;
my @remade_data;
@remade_data[(map { $stored{$_}{order} } keys %stored)] = keys %stored;

As you can see, sorting does not occur in this piece of code, just a conversion.

Answer 4

I think this is nothing more than an insertion sort.