Discrete math problem

1. Use decision trees to find a lower bound on the number of comparisons required to sort six items in the worst case.

The decision tree would be a binary tree.

It would contain n! leaves.

Equivalently it has at least 1+lg(n!) levels.

Worst case would be lg(n!).

n! = 6! = 720 = lg(720) = 9.49 = 10 comparisons

Give an algorithm that uses this number of comparisons to sort six items in the worst case.