The mean would certainly be n! (note that it is possible, and even likely, that you may create the same sorting multiple times by random chance). The median, w

The mean would certainly be n! (note that it is possible, and even likely, that you may create the same sorting multiple times by random chance). The median, which I don't think you're referring to, is something else (I imagine it would be substantially less than the mean). (See http://en.wikipedia.org/wiki/Geometric_distribution http://en.wikipedia.org/wiki/Geometric_distribution)