Your solution is not guaranteed to be well shuffled since you relying on sort to shuffle ties.

By using sort, you've converted a O(N) problem into an O(N log N) problem. That can make a substantial difference in execution time. In other words, your solution is less scalable.

Something which isn't scalable could still be fast for smaller input set, but it's not even the case here:

>perl script.pl 50

             Rate mrborisguy    ikegami
mrborisguy 2074/s         --       -51%
ikegami    4225/s       104%         --    # Without XS.

              Rate mrborisguy    ikegami
mrborisguy  2167/s         --       -91%
ikegami    23688/s       993%         --   # With XS.
[download]

And for an array of 1700, as relevant here:

>perl script.pl 1700

             Rate mrborisguy    ikegami
mrborisguy 31.0/s         --       -74%
ikegami     120/s       286%         --    # Without XS.

             Rate mrborisguy    ikegami
mrborisguy 31.7/s         --       -96%
ikegami     722/s      2179%         --    # With XS.
[download]

The benchmark script:

use strict;
use warnings;

use Benchmark  ();
use List::Util ();

sub mrborisguy {
   my @shuffled = map { $_->[1] }
                  sort { $a->[0] <=> $b->[0] }
                  map { [rand(),$_] }
                  @{$_[0]};
}


sub ikegami {
   my @shuffled = List::Util::shuffle(@{$_[0]});
}


{
   my @data = map { [] } 1..$ARGV[0];

   Benchmark::cmpthese(-3, {
      mrborisguy => sub { mrborisguy \@data },
      ikegami    => sub { ikegami    \@data },
   });
}
[download]

Update: Added benchmarks to back my statements.