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.
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