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