perl - 0-65535 整数最快的排序算法是什么？

Question

我必须对一些整数进行排序，这些整数的值介于 30.000.000 和 350.000.000 之间。将有 0 到 65.535 个整数，平均数为 20.000。 RAM 使用无关紧要，速度很重要。

稍后我还必须将它们分成几组，只要其中两个值之间的差距大于 65.535，就会始终设置分界线，这正是我需要算法的原因。

如果有任何不同，该算法将在 Perl 脚本中使用。

编辑:经过深思熟虑并阅读了答案后，我开始意识到一件事:我实际上并不关心数据本身。因为我真的只想找到具有小间隙的组的开始和结束值，所以排序只需要创建桶并且可以丢弃数据。

Edit2:经过一些测试和尝试提供的答案后，我发现最快的方法是:

my @sort = sort {$a <=> $b} @item_offsets;
my @buckets;
my $start = shift @sort;
push @buckets, [$start,$start];
for my $item ( @sort ) {
    if ( $item < $buckets[$#buckets][1]+$gap ) {
        $buckets[$#buckets][1] = $item;
    }
    else {
        push @buckets, [$item,$item];
    }
}
say $#buckets;

Answer 1

我只是在运行算法之前制作了一个桶数组，每组一个桶对应 65536 个连续值。桶将包含其内容的最小值和最大值，但不会存储内容本身。运行算法后，对桶进行单次传递。如果有两个连续的非空桶且 min(bucket2)-max(bucket1) < 65536，则合并它们。在算法完成运行之前不会发生合并。丢弃任何空桶。该算法是线性时间的。

注意Bucket Sort .