A binary tree belongs to each comparison-oriented sorting algorithm. The branches of this decision tree correspond to the alternatives in the program flow, which result from pairwise key comparisons. Such a decision tree is to be supplemented by an additional information: Each node shall be labeled with the order in which the keys in the field have been placed at this point in time. As an example we consider an insertion sort of four keys (s1, . . . ,s4). The root is then labeled with (s1,s2,s3,s4), an inner node e.g. with (s3,s1,s4,s2), the edges starting from it each with the possible outputs of the pending key comparison: (si sj ),(si > sj ). The leaves then contain an ordered sequence, e.g., (s2 s1 s3 s4). Specify the subtree of the decision tree of insertion-sort that results for case s1 < s2.

The two paths to be followed are those for (22,27,13,8) and (3,17,32,10), respectively.