Well, I pointed to the link with the discussion:
http://kw.pm.org/wiki/index.cgi?ListShuffle
...but here is a quick summary.

Your algorithm (and my mostly equivalent one) are memory expensive because they have to allocate for a random number for each element in the list. If you are sorting numbers, this amounts to a doubling of the memory footprint.

It is slow because it is two pass, the first O(N), the second (the sort) O(NlogN). That's not terribly slow, but list shuffling can be accomplished with O(N) running time. So, a pure perl swap-shuffle is about 4 times faster, and the List::Util version is about 70 times faster, depending, of course on list-size.