# Decision Tree

Updated:

less than 1 minute read

• In terms of decision trees, we assume without loss of generality that all elements are distinct.
• A decision tree is a full binary tree that 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 correct
• Corollary 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

Tags: