You could, in principle, rearrange any number of additional arrays along with brr, but this becomes wasteful as the number of such arrays becomes large. The preferred technique is to make use of an index table, as described in §. | 336 Chapter 8. Sorting You could in principle rearrange any number of additional arrays along with brr but this becomes wasteful as the number of such arrays becomes large. The preferred technique is to make use of an index table as described in . CITED REFERENCES AND FURTHER READING Sedgewick R. 1978 Communications of the ACM vol. 21 pp. 847-857. 1 Heapsort While usually not quite as fast as Quicksort Heapsort is one of our favorite sorting routines. It is a true in-place sort requiring no auxiliary storage. It is an N log2 N process not only on average but also for the worst-case order of input data. In fact its worst case is only 20 percent or so worse than its average running time. It is beyond our scope to give a complete exposition on the theory of Heapsort. We will mention the general principles then let you refer to the references 1 2 or analyze the program yourself if you want to understand the details. A set of N numbers a i 1 . . N is said to form a heap if it satisfies the relation aj 2 aj for 1 j 2 j N Here the division in j 2 means integer divide . is an exact integer or else is rounded down to the closest integer. Definition will make sense if you think of the numbers a as being arranged in a binary tree with the top boss node being a1 the two underling nodes being a2 and a3 their four underling nodes being a4 through a7 etc. See Figure . In this form a heap has every supervisor greater than or equal to its two supervisees down through the levels of the hierarchy. If you have managed to rearrange your array into an order that forms a heap then sorting it is very easy You pull off the top of the heap which will be the largest element yet unsorted. Then you promote to the top of the heap its largest underling. Then you promote its largest underling and so on. The process is like what happens or is supposed to happen in a large corporation when the chairman of the board retires. You then repeat the whole process by retiring .
