Daniel I. Lewis, as I said, lists can have structure even when that structure is not chosen by a person.
“Let’s say, for the sake of argument, that you get sorted lists (forwards or backwards) more often than chance, and the rest of the time you get a random permutation.”
Let’s not say that, because it creates an artificial situation. No one would select randomly if we could assume that, yet random selection is done. In reality, lists that are bad for selecting from the middle are more common than by random chance, so random beats middle.
If you put the right kind of constraints on the input, it’s easy to find a nonrandom algorithm that beats random. But those same constraints can change the answer. In your case, part of the answer was the constraint that you added.
I was hoping for an answer to the real-world situation.
GreedyAlgorithm,
That’s actually the scenario I had in mind, and I think it’s the most common. Usually, when someone does a sort, they do it with a general-purpose library function or utility.
I think most of those are actually implemented as a merge sort, which is usually faster than quicksort, but I’m not clear on how that ties in to the use of information gained during the running of the program.
What I’m getting at is that the motivation for selecting randomly and any speedup for switching to merge sort don’t seem to directly match any of the examples already given.
In his explanation and examples, Eliezer pointed to information gained while the algorithm is running. Choosing the best type of selection in a quicksort is based on foreknowledge of the data, with random selection seeming best when you have the least foreknowledge.
Likewise, the difference between quicksort and other sorts that may be faster doesn’t have an obvious connection to the type information that would help you choose between different selections in a quicksort.
I’m not looking for a defense of nonrandom methods. I’m looking for an analysis of random selection in quicksort in terms of the principles that Eliezer is using to support his conclusion.