Is there a name for this sort?

Question

What is the name for the sort used in this answer? I Googled for "perfect insertion sort" but didn't find anything. Here is the code from that 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 it's nothing but an insertion sort.

Answer 2

I think I probably should have named that perfect_bucket_sort instead of perfect_insertion_sort.

Answer 3

This isn't insertion sort, in fact it's not even a comparison sort because the theoretical lowest bound for those is O(nlogn).

So it's probably bucket sort; also notice there are no comparisons made :)

Answer 4

It's not really a sort at all. it is, in fact, primarily a map or a transformation. This is an example of the data structure they have:

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

It's simply a translation of 'order' to elements in an array. For example, if you pass in this $hash to perfect_insert_sort, it will return a 67 element array, with three items (one at index 3, one at 20, and one at 66) and the rest being undef, and entirely in an unsorted order.

Nothing about that function does any sorting of any kind. If there is any sorting going on in that other answer, it's happening before the function is called.

@downvoter:

And looking at the other answer, the sorting happens at insertion time. THAT component might be considered a sort. This subroutine, however, does not create that order - it merely reconstitutes it.

Take a look at the classical definition for a sort:

1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order)
2. The output is a permutation, or reordering, of the input.

Part 2 is certainly being satisfied: there is a transformation of the hash structure to a list going on. However, part 1 is not satisfied. There is no determining of order going on. The order has been predetermined during insertion. If this were a 'sort', then the following would also be a sort:

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, there is no sorting going on in that chunk of code, merely transformation.