Find the least number of comparisons needed to sort five elements and devise an algorithm that sorts these elements using this number of comparisons.
The tournament sort is a sorting algorithm that works by building an ordered binary tree. We represent the elements to be sorted by vertices that will become the leaves. We build up the tree one level at a time as we would construct the tree representing the winners of matches in a tournament. Working left to right, we compare pairs of consecutive elements, adding a parent vertex labeled with the larger of the two elements under comparison. We make similar comparisons between labels of vertices at each level until we reach the root of the tree that is labeled with the largest element. The tree constructed by the tournament sort of 22, 8, 14, 17, 3, 9, 27, 11 is illustrated in part
(a) of the figure. Once the largest element has been determined, the leaf with this label is relabeled by -∞, which is defined to be less than every element. The labels of all vertices on the path from this vertex up to the root of the tree are recalculated, as shown in part
(b) of the figure. This produces the second largest element. This process continues until the entire list has been sorted.
