# Decision Tree

** Updated:**

- In terms of decision trees, we assume without loss of generality that all elements are distinct.
- A decision tree is a
full binary treethat represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.- any correct sorting algorithm must be able to produce
each permutation of its input, each of the n! permutations on n elements must appear as one of the leaves of the decision tree for a comparison sort to be correctCorollary 8.2:Heapsort and merge sort are asymptotically optimal comparison sorts.

—— CLRS

*Tips for this figure:*

- The algorithm shown in this figure is insertion sort where we iterate
`j`

and`i = j - 1`

- the worst-case comparisons for a comparison algorithm = the height of the decision tree

## Leave a comment