I very strongly feel that JUnit shouldn't ship with a random sorting implementation. Instead we should allow users to provide their own implementations.

Randomly sorting tests seems like a good idea, but it often isn't
- if a particular ordering causes the tests to fail, running again will fix them. so the failures are not reproducible
- if you are making a change to your code, and then run the tests, and you happen to hit an ordering that causes your test to fail, then most likely you'll assume your code changes caused the failure, leading you in the wrong direction
- related to the previous point, if someone checks in a change, and the next run of your build happens to hit an order that causes a failure, you'll think incorrectly that the change broke the build
- randomly ordering tests isn't a sort. it's really hard to get a random ordering in a way that won't cause an infinite loop, or won't be slow, or won't cause the ordering to change in the middle of the run

There are ways around some of these
- you could print out the random seed used, and have a way to specify the seed. but there are a dozen ways one could do each of these, and I'm not sure JUnit should pick which one is best
- you could have the random seed based on the time of day (so, perhaps it changes daily). but I'm not sure JUnit should decide when the seed should change (or, again, how to specify a seed so you can reproduce)

I'd be more than happy to allow users to specify their own sorting class, and for the documentation to provide a suggested implementation that does random sorting (as long as it gives the above caveats)