first component)then their relative order in the starting sequence (which is sorted by the second componentis preserved thusthe resulting sequence is guaranteed to be sorted lexicographically every time we leave to simple exercise ( - the determination of how this approach can be extended to triples and other -tuples of numbers we can summarize this section as followsproposition let be sequence of key-value pairseach of which has key ( , , )where is an integer in the range [ , for some integer > we can sort lexicographically in time ( ( )using radix-sort as important as it issorting is not the only interesting problem dealing with total order relation on set of elements there are some applicationsfor examplethat do not require an ordered listing of an entire setbut nevertheless call for some amount of ordering information about the set before we study such problem (called "selection")let us step back and briefly compare all of the sorting algorithms we have studied so far comparison of sorting algorithms at this pointit might be useful for us to take breath and consider all the algorithms we have studied in this book to sort an -element array listnode listor general 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 (nlogn)-time behaviorincluding heap-sortmerge-sortand quick-sort finallywe have studied special class of sorting algorithmsnamelythe bucket-sort and radix-sort methodsthat 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 the sorting algorithm best suited for particular application depends on several properties of that application 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 orderthus