Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?

Question

I am reading an algorithm book.

Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements.

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated for $n$?

• Rinkesh P: any reason you feel you can't create one?
• tchappy ha: @RinkeshP Thank you very much for your comment. I saw decision tree for insertion sort with $n=3$ on p.283 (Fig. 8.23) in "Data Structures and Algorithms" by Aho, Hopcroft and Ullman. But for example I cannot create a decision tree for quicksort since quicksort is complicated.
• Rinkesh P: I think you confused the decisions taken by the algorithm with decision tree. While proving the lower bound for sorting we do not care about how the sorting would take place, other than the least no. of comparisons to sort the input.
• tchappy ha: @RinkeshP Thank you very much for your comment.

Answer 1

In general, a decision tree would enumerate all possible permutations $(N!)$ for given input of $N$ elements, out of which only 1ドル$ would be desirable.

A sorting algorithm doesn't generate all possible permutations, it follows a set of predefined steps to reach the desired output. This would be equivalent to taking a path in the decision tree from the root to the leaf which represents the sorted permutation. And if you follow the algorithm, you will always follow the same path.

• tchappy ha: Rinkesh P, Thank you very much for your answer.

Answer 2

The procedure below can be used to explicitly build the decision tree of any comparison-based algorithm:

• generate all permutations of the array $[1, 2, \cdots n]$.

• for every permutation, run the algorithm and note the outcomes of every comparison, together with the involved element indexes.

• merge the traces so obtained, in the form of a tree.

Below all traces of InsertionSort on four elements:

1≥0 2≥1 3≥2 
1≥0 2≥1 3<2 3≥1 
1≥0 2≥1 3<2 3<1 3≥0 
1≥0 2≥1 3<2 3<1 3<0 
1≥0 2<1 2≥0 3≥2 
1≥0 2<1 2≥0 3<2 3≥1 
1≥0 2<1 2≥0 3<2 3<1 3≥0 
1≥0 2<1 2≥0 3<2 3<1 3<0 
1≥0 2<1 2<0 3≥2 
1≥0 2<1 2<0 3<2 3≥1 
1≥0 2<1 2<0 3<2 3<1 3≥0 
1≥0 2<1 2<0 3<2 3<1 3<0 
1<0 2≥1 3≥2 
1<0 2≥1 3<2 3≥1 
1<0 2≥1 3<2 3<1 3≥0 
1<0 2≥1 3<2 3<1 3<0 
1<0 2<1 2≥0 3≥2 
1<0 2<1 2≥0 3<2 3≥1 
1<0 2<1 2≥0 3<2 3<1 3≥0 
1<0 2<1 2≥0 3<2 3<1 3<0 
1<0 2<1 2<0 3≥2 
1<0 2<1 2<0 3<2 3≥1 
1<0 2<1 2<0 3<2 3<1 3≥0 
1<0 2<1 2<0 3<2 3<1 3<0

• tchappy ha: Yves Daoust, Thank you very much for your answer.

Answer 3

In theory, yes you should be able to create a decision tree for every comparison based sorting algorithm. You can write a program that will do so (for a fixed comparison-based sorting algorithm of your choice, say quicskort). Do keep in mind that decision trees have n! leaves so (roughly) beyond input sizes of say 11 you will run into storage issues.

Comparison-based sorting is defined rather informally, so to give a complete answer: it may get super complicated to detect whether an algorithm is truly comparison based (even before considering to generate the tree) and there is no formal logic I know of to verify the comparison-based property (would love to find out if someone did it). On the other hand, for most algorithms that are considered in practice the comparison-based property is straightforward to verify, ie quicskort, mergesort and heapsort among several others are easily checked to be comparison based and hence you can produce a decision tree (for small input sizes).

• tchappy ha: Michel, Thank you very much for your answer.
• user16034: I wonder why you make this discussion about comparison-baseness. In fact, any sorting algorithm can be put in the form of a decision tree.
• ExpressionCoder: @YvesDaoust what is the "decision tree" of bucket sort? Decision trees are the tool used to represent the computational paths of comparison-based algorithms
• user16034: @Michel: you can see that in several ways. First, bucket sort can be implemented with comparisons. Second you can consider that assigning the keys to bucket is a "non-decision process" and the tree is void; but you can very well consider that the choice of a bucket is the outcome of a decision, and you get a $b$-ary tree. That's a matter of convention.
• ExpressionCoder: Sure. Convention is all well. The aim is to extract useful info on timing. To avail of lower bounds you need to verify the comparison based property even in complex cases, based on a definition of "comparison-based" that is far too informal. Your mileage may differ.