chap internal sorting compared with xagainthere are two possibilities if is less than xthen these items should be swapped (the left branchif is not less than xthen insertion sort is complete (the right branchnote that the right branch reaches leaf nodeand that this leaf node contains only permutation yxz this means that only permutation yxz can be the outcome based on the results of the decisions taken to reach this node in other wordsinsertion sort has "foundthe single permutation of the original input that yields sorted list likewiseif the second decision resulted in taking the left brancha third comparisonregardless of the outcomeyields nodes in the decision tree with only single permutations againinsertion sort has "foundthe correct permutation that yields sorted list any sorting algorithm based on comparisons can be modeled by decision tree in this wayregardless of the size of the input thusall sorting algorithms can be viewed as algorithms to "findthe correct permutation of the input that yields sorted list each algorithm based on comparisons can be viewed as proceeding by making branches in the tree based on the results of key comparisonsand each algorithm can terminate once node with single permutation has been reached how is the worst-case cost of an algorithm expressed by the decision treethe decision tree shows the decisions made by an algorithm for all possible inputs of given size each path through the tree from the root to leaf is one possible series of decisions taken by the algorithm the depth of the deepest node represents the longest series of decisions required by the algorithm to reach an answer there are many comparison-based sorting algorithmsand each will be modeled by different decision tree some decision trees might be well-balancedothers might be unbalanced some trees will have more nodes than others (those with more nodes might be making "unnecessarycomparisonsin facta poor sorting algorithm might have an arbitrarily large number of nodes in its decision treewith leaves of arbitrary depth there is no limit to how slow the "worstpossible sorting algorithm could be howeverwe are interested here in knowing what the best sorting algorithm could have as its minimum cost in the worst case in other wordswe would like to know what is the smallest depth possible for the deepest node in the tree for any sorting algorithm the smallest depth of the deepest node will depend on the number of nodes in the tree clearly we would like to "push upthe nodes in the treebut there is limited room at the top tree of height can only store one node (the root)the tree of height can store three nodesthe tree of height can store seven nodesand so on here are some important facts worth remembering