I have written a simple sorting algorithm and would like to know what type is it? It just maps the initial array's elements into an empty array with the indexes of the values of the initial elements.

my @arg = (5, 14, 12, 9, 1, 17, 3, 19, 20, 4, 6, 15, 8, 18, 7, 2, 10, 13, 11, 16);
my @out;
map { $out[$_] = $_ } @arg;
print join " ", @out;

Sure there can be added shrinking to the output array as in the real world there can be holes in indexes. Also, this example can be extended for working with doubles. For this sake, I would suggest using other data structures (i.e.: trees or linked lists)

UPDATE

Benchmarks:

                   Rate uniqsort   bubble  mapping perlsort
    uniqsort  82274/s       --     -29%     -87%     -90%
    bubble   115925/s      41%       --     -81%     -86%
    mapping  614399/s     647%     430%       --     -25%
    perlsort 814352/s     890%     602%      33%       --

• &uniqsort - using List::MoreUtils via uniq sort @arr;
• &bubble - the basic bubble sort
• &mapping - this one
• &perlsort - using sort {$a<=>$b} @arr

CodePudding user response：

First of all, that doesn't sort the values because it produces the following:

undef, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Note the extra element. It's a partially broken (no filtering of empty elements), partially specialized (no duplicates allowed) version of pigeonhole sort.

By the way,

@out[@arg] = @arg;

should be faster than

map { $out[$_] = $_ } @arg;