Re: Generation of permutations

[dewar@gnat.com (Robert Dewar)]

"Marin David Condic" > A better (slower) algorithm would be > to
generate a random set of machine
> instructions, execute them, see if it sorted the list
                              ^^^

You could see if it sorted some particular list, but to
determine whether a set of instructions constitutes a
general sorting algorithm is obviously recursively
undecidable. So this is not a well formed method.

Incidentally while we are at it, consider the following
sorting algorithm which is guaranteed to do the minimal
number of comparisons under all circumstances:

Step 1. Determine number of items to be sorted

Step 2. Enumerate all binary decision trees for sorting
this number of items.

Step 3. Choose the decision tree with the minimum depth

Step 4. Use this tree to sort the data