Decision Tree

⚠️ This post was created when I was in high school and is no longer maintained.

• In terms of decision trees, we assume without loss of generality that all elements are distinct.
• A decision tree is a full binary tree representing the element comparisons a specific sorting algorithm makes on an input of a given size.
• Any correct sorting algorithm must be able to produce every permutation of its input. Each of the n! permutations on n elements appears as a leaf of the decision tree for a comparison sort to be correct.
• Corollary 8.2: Heapsort and merge sort are asymptotically optimal comparison sorts.
  —— CLRS

Tips for this figure:

• The algorithm shown here is insertion sort, iterating with j and i = j - 1.

---

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