Каков самый быстрый алгоритм сортировки для 0-65535 целых чисел?

Я использовал бы вид основания, так как необходимо сгруппировать вывод.

Маловероятно, что Вы сможете записать алгоритм сортировки в Perl, который будет работать лучше, чем встроенный Perl sort функция:

@numbers = sort {$a <=> $b} @numbers;

Можно экспериментировать с прагмой вида, чтобы видеть, лучше ли конкретный алгоритм:

use sort '_quicksort';
use sort '_mergesort';

Так как Ваши точки разделения будут варьироваться в зависимости от распределения данных, я думаю, что необходимо отсортировать весь список сначала затем цикл по нему, чтобы сделать вырезание.

my $prev  = shift @numbers;  # already sorted
my @group = [$prev];
my $i     = 0;

foreach my $n (@numbers) {
    $i++ if ($n - $prev > 65535);
    push @{$group[$i]}, $n;
    $prev = $n;
}

Я просто собирался сказать вид основания, http://en.wikipedia.org/wiki/Radix_sort однако, который мог быть немного, выше какого Вы надеялись реализовывать, Introsort обычно является принятым решением для сортировки для данных http://en.wikipedia.org/wiki/Introsort, это - изменение quicksort, который переключается для пирамидальной сортировки, когда это достигает меньших наборов, поскольку это быстрее на меньших наборах, чем quicksort.

Я попробовал бы это:

my @sorted = map { unpack "N" } sort map { pack "N" } @unsorted;

Если Вы используете число в качестве индекса к массиву и затем увеличиваете количество того положения, Вы "сгруппировали" их и сделали это в одной передаче.

в псевдокоде:

while(morenumbers)
  sorted[[unsorted[number]]++
  number++

Если диапазон знается заранее, можно уменьшить, индексируют значения (например, значение 30000 для обеспечения его в правильный диапазон).