comparing sorting algorithms at this pointit might be useful for us to take moment and consider all the algorithms we have studied in this book to sort an -element sequence considering running time and other factors we have studied several methodssuch as insertion-sortand selection-sortthat have ( )-time behavior in the average and worst case we have also studied several methods with ( log )-time behaviorincluding heap-sortmerge-sortand quick-sort finallythe bucket-sort and radix-sort methods run in linear time for certain types of keys certainlythe selection-sort algorithm is poor choice in any applicationsince it runs in ( time even in the best case butof the remaining sorting algorithmswhich is the bestas with many things in lifethere is no clear "bestsorting algorithm from the remaining candidates there are trade-offs involving efficiencymemory usageand stability the sorting algorithm best suited for particular application depends on the properties of that application in factthe default sorting algorithm used by computing languages and systems has evolved greatly over time we can offer some guidance and observationsthereforebased on the known properties of the "goodsorting algorithms insertion-sort if implemented wellthe running time of insertion-sort is ( )where is the number of inversions (that isthe number of pairs of elements out of orderthusinsertion-sort is an excellent algorithm for sorting small sequences (sayless than elements)because insertion-sort is simple to programand small sequences necessarily have few inversions alsoinsertion-sort is quite effective for sorting sequences that are already "almostsorted by "almost,we mean that the number of inversions is small but the ( )-time performance of insertion-sort makes it poor choice outside of these special contexts heap-sort heap-sorton the other handruns in ( log ntime in the worst casewhich is optimal for comparison-based sorting methods heap-sort can easily be made to execute in-placeand is natural choice on smalland medium-sized sequenceswhen input data can fit into main memory howeverheap-sort tends to be outperformed by both quick-sort and merge-sort on larger sequences standard heap-sort does not provide stable sortbecause of the swapping of elements