Comp 122

linsort - 5

Lin / Devi

Comp 122

# Decision Tree (Contd.)

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.