I wrote : > > ...in this sense, it is clear that quicksort for instance is optimal* > > It is easy to see, when you detail this algorithm, that never during its > run is the result of a comparison it makes, preordained by comparisons > already made; iow : it doesn't make superfluous or redundant comparisons.
The above is true, but... While an algorithm may never call for a comparison that has a result predetermined by previous comparisons, it doesn't follow that the property would hold true for the exact same comparisons done in a different order. In particular, any sort algorithm must have compared successive items to be able to conclude to their order, so that any system of comparisons that allows to sort a dataset of n items, must contain the strictly minimal system of n-1 comparisons of successive items. This doesn't change the conclusion that an algorithm that never does a comparison with a result that could be deduced from previous comparisons, will only sample a random comparison function up to a system of comparisons that's consistent with an order relation between the items. -- http://mail.python.org/mailman/listinfo/python-list