Problem
1. Draw the comparison trees for (a) insertion sort and (b) selection sort applied to four objects.
2. (a) Find a sorting method for four keys that is optimal in the sense of doing the smallest possible number of key comparisons in its worst case.
(b) Find how many comparisons your algorithm does in the average case (applied to four keys). Modify your algorithm to make it come as close as possible to achieving the lower bound of lg 4! ≈ 4.585 key comparisons. Why is it impossible to achieve this lower bound?