chap internal sorting and quicksortby taking advantage of the best case behavior of another algorithm (insertion sortwe'll see several examples of how we can tune an algorithm for better performance we'll see that special case behavior by some algorithms makes them the best solution for special niche applications (heapsortsorting provides an example of significant technique for analyzing the lower bound for problem sorting will also be used to motivate the introduction to file processing presented in the present covers several standard algorithms appropriate for sorting collection of records that fit in the computer' main memory it begins with discussion of three simplebut relatively slowalgorithms requiring th( time in the average and worst cases several algorithms with considerably better performance are then presentedsome with th( log nworst-case running time the final sorting method presented requires only th(nworst-case time under special conditions the concludes with proof that sorting in general requires ohm( log ntime in the worst case sorting terminology and notation except where noted otherwiseinput to the sorting algorithms presented in this is collection of records stored in an array records are compared to one another by requiring that their type extend the comparable class this will require that the class implements the compareto methodwhich returns value less than zeroequal to zeroor greater than zero depending on its relationship to the record being compared to the compareto method is defined to extract the appropriate key field from the record we also assume that for every record type there is swap function that can interchange the contents of two records in the array given set of records rn with key values kn the sorting problem is to arrange the records into any order such that records rs rs rsn have keys obeying the property ks <ks <<ksn in other wordsthe sorting problem is to arrange set of records so that the values of their key fields are in non-decreasing order as definedthe sorting problem allows input with two or more records that have the same key value certain applications require that input not contain duplicate key values the sorting algorithms presented in this and in can handle duplicate key values unless noted otherwise when duplicate key values are allowedthere might be an implicit ordering to the duplicatestypically based on their order of occurrence within the input it might be desirable to maintain this initial ordering among duplicates sorting