sorting heapsort was invented by williams [ ]floyd [ provided the linear-time algorithm for heap construction theorem is from [ an exact average-case analysis of mergesort has been described in [ an algorithm to perform merging in linear time without extra space is described in [ quicksort is from hoare [ this paper analyzes the basic algorithmdescribes most of the improvementsand includes the selection algorithm detailed analysis and empirical study was the subject of sedgewick' dissertation [ many of the important results appear in the three papers [ ][ ]and [ [ provides detailed implementation with some additional improvementsand points out that older implementations of the unix qsort library routine are easily driven to quadratic behavior exercise is from [ decision trees and sorting optimality are discussed in ford and johnson [ this paper also provides an algorithm that almost meets the lower bound in terms of number of comparisons (but not other operationsthis algorithm was eventually shown to be slightly suboptimal by manacher [ the selection lower bounds obtained in theorem are from [ the lower bound for finding the maximum and minimum simultaneously is from pohl [ the current best lower bound for finding the median is slightly above comparisons due to dor and zwick [ ]they also have the best upper boundwhich is roughly comparisons [ external sorting is covered in detail in [ stable sortingdescribed in exercise has been addressed by horvath [ bentley and mcelroy"engineering sort function,software--practice and experience ( ) - dor and zwick"selecting the median,siam journal on computing ( ) dor and zwick"median selection requires ( ) comparisons,siam journal on discrete math ( ) - floyd"algorithm treesort ,communications of the acm ( ) ford and johnson" tournament problem,american mathematics monthly ( ) - fussenegger and gabow" counting approach to lower bounds for selection problems,journal of the acm ( ) - golin and sedgewick"exact analysis of mergesort,fourth siam conference on discrete mathematics gonnet and baeza-yateshandbook of algorithms and data structures ed addison-wesleyreadingmass hibbard"an empirical study of minimal storage sorting,communications of the acm ( ) - hoare"quicksort,computer journal ( ) - horvath"stable sorting in asymptotically optimal time and extra space,journal of the acm ( ) - huang and langston"practical in-place merging,communications of the acm ( ) - incerpi and sedgewick"improved upper bounds on shellsort,journal of computer and system sciences ( ) -