Every sorting algorithm has an associated decision tree. That is$,$ suppose on an input of a givensize the algorithm first compares a$23$ to a$12.$ We could represent this as a tree where the root iswhere we start, and, having found out whether or not a$2$s $<412,$ we either take the left branchor the right branch. Each of those branches leads to another node with another comparison to bedone. After some sequence of comparisons, we get to a leaf node, which represents a particularpermutation of the input data, which tells us the sorted order.