Sheesh! What kind of hardware do you have? It's taking me longer to execute it than it took you to write it!

:-)

Okay, after 14 minutes (!), I saw similar results. The problem, as I see it, is not the distribution around the median, but the predictability of successive elements.

Any given number may have an equal chance of being at any location in the result array. However, there seems to be a very large probability (certainly greater than random) that for a given element, the element which starts next to this one will end up very close to wherever this element ends up.
At least in the case of pre-sorted input (which we all used), close neighbors tend to not only stay near each other, but to stay in the same order. Given that Perl uses a quicksort-based implementation, this will likely be true of all input data.

Obviously, neither of the two solutions (the original post and this one) is suitable for strong cryptography (no solution which only uses a pseudo-random number generator will be).

Russ