Sorting (HPSORT/EXHEAP)

This chapter presents an algorithm for sorting. A frequently occurring problem in combinatorial work is the sorting of an array. There are various criteria by which a person may evaluate the effectiveness of a sorting method, such as the average amount of labor (pairwise comparisons or displacements of position) required to sort an array of length n , the maximum amount of labor required by some sequence of length n , the amount of array storage required, the amount by which the method takes advantage of whatever order is already present in the input list, and elegance, compactness, universality, etc. No single sorting method optimizes all departments at once. The algorithm presented in the chapter is a good choice if just one general-purpose sort is to be available for combinatorial applications. It requires an average of cn log n operations, a maximum of cn log n operations, no array storage other than the input array, and it is extremely elegant, compact, and universal. The chapter discusses the Heapsort algorithm, which is divided into two phases: (1) the input array is transformed into a heap and (2) the heap is sorted into nondecreasing order.