linsort - 5
Lin / Devi
Execution of sorting algorithm corresponds to tracing a path from root to leaf.
The tree models all possible execution traces.
At each internal node, a comparison ai aj is made.
If ai aj, follow left subtree, else follow right subtree.
View the tree as if the algorithm splits in two at each node, based on information it has determined up to that point.
When we come to a leaf, ordering a(1) a (2) … a (n) is established.
A correct sorting algorithm must be able to produce any permutation of its input.
Hence, each of the n! permutations must appear at one or more of the leaves of the decision tree.