try1a => sub {
        my $high = my @list = sort { $a <=> $b } @input;
        my $mid = my $low = 0;
        $list[$mid = $low + $high >> 1] < 0 ?
          ($low = $mid + 1) : ($high = $mid) while $low < $high;
        push @list, splice @list, 0, $low;
        Compare(\@list,\@output) or die "@list" if DO_CHECK;
    },
[download]

Grumble... I hate speed contests :(

Although that "push" line is quite interesting. perl++