Given a comparison$-$based sorting algorithm $($e$.$g$.,$ QuickSort$),$ and the array $[4,8,1,5],$ draw the decision tree that represents ALL POSSIBLE COMPARISONS between the elements.

$$ Internal nodes

correspond to yes$/$no

questions.

$$ Each internal node has

two children, one for

$$yes$$ and one for $$no$.$

$$ Leaf nodes correspond

to outputs.

$$ In this case, all possible

orderings of the items.

$$ Running an algorithm

on a particular input

corresponds to a

particular path through

the tree.