If using CPAN is allowed, see Sort::Packed, this is faster:

# ...
use Sort::Packed 'sort_packed';
# ...
    sort_packed => sub {
        sort_packed I => my $s = pack 'i*', @input;
        my @list = unpack 'i*', $s;
        Compare(\@list,\@output) or die "@list" if DO_CHECK;
    },
# ...
[download]

Edit: As I see now, I omitted copying @input list to unnecessary intermediate @list, as all contestants, it seems, are bound to do. To be fair, either everybody drop that line, or it's inserted into code above. Still, Sort::Packed is faster and scales better. Sorry, didn't measure other monks' answers from last night on. Surprise is counter-intuitive good speed of Discipulus' simple just-push-in-loop solution. + All tricks with sign bit interpretation sacrifice integer range (Veltro++).