Brian: FYI, mergesort isn't faster than a good quicksort. Skiena's The Algorithm Design Manual, for example, says that "experiments show that a where a properly implemented quicksort is implemented well, it is typically 2-3 times faster than mergesort or heapsort" (2nd ed., p. 129).
I'm still waiting to hear what Eliezer says about your example too, as quicksort does seem to be an example of the best known implementation making necessary use of (pseudo-) randomness, and quicksort is of course extremely well-understood.
Smallwood: how could you determine that the AI provided the actual source code rather than very similar source code that has been subtly altered so as to ensure "good" behavior once it is let out of the simulated box?
It is a bias because it is a prior assumption rather than something that is learned in the course of training. Mitchell's Machine Learning has a very clear explanation of inductive bias and why it is necessary for learning to occur. There are some examples of inductive bias at Wikipedia: http://en.wikipedia.org/wiki/Inductive_bias