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.
Daniel I. Lewis, as I said, lists can have structure even when that structure is not chosen by a person.
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.