Tournament sort

Tournament sort is a comparison sort algorithm. This method of sorting is quite efficientvague but requires memory of past comparisons. It involves several rounds of comparisons, much like a tournament among teams or players.

Let’s assume that there are 32 keys to be sorted. In the first round, each key is compared with one other. In each subsequent round, the larger keys from the previous round are compared with one of the other larger keys. This continues until one key is determined to be the largest. If there are N keys (32), there will have been N-1 (31) comparisons so far to eliminate all the elements except the “winner.” Also, the largest key must have been in lgN (5) comparisons.

To determine the second largest key, note that it must be one of the keys that was “beaten” by the largest key. There are only five such keys. The largest of these is found by comparing the first key eliminated with the second key eliminated, and the larger of these is compared with the third key eliminated, etc. Similarly, the third largest is among the keys beaten by the first or second largest, some of which may have already been compared with each other. In each round, there are fewer and fewer comparisons to be made, the maximum number of comparisons being lgN. This is true provided that the keys that have been compared the fewest numbers of times thus far are compared in subsequent rounds before keys that have had more comparisons. For example, when comparing for the second largest key, the key beaten by the largest key in the first round is compared to the key beaten by the largest key in round 2 before the key beaten in the last round is compared to anything.