sorting and selection to gain intuition before answering this questionwe consider the following example example consider the following sequence (we show only the keys) (( )( )( )( )( )( )( )( )if we sort stably on the first componentthen we get the sequence (( )( )( )( )( )( )( )( )if we then stably sort this sequence using the second componentwe get the sequence , (( )( )( )( )( )( )( )( ))which is unfortunately not sorted sequence on the other handif we first stably sort using the second componentthen we get the sequence (( )( )( )( )( )( )( )( )if we then stably sort sequence using the first componentwe get the sequence , (( )( )( )( )( )( )( )( ))which is indeed sequence lexicographically ordered sofrom this examplewe are led to believe that we should first sort using the second component and then again using the first component this intuition is exactly right by first stably sorting by the second component and then again by the first componentwe guarantee that if two entries are equal in the second sort (by the 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 ( kd )where ki is an integer in the range [ for some integer > we can sort lexicographically in time ( ( )using radix-sort radix sort can be applied to any key that can be viewed as composite of smaller pieces that are to be sorted lexicographically for examplewe can apply it to sort character strings of moderate lengthas each individual character can be represented as an integer value (some care is needed to properly handle strings with varying lengths