radix-sort one of the reasons that stable sorting is so important is that it allows the bucket-sort approach to be applied to more general contexts than to sort integers supposefor examplethat we want to sort entries with keys that are pairs ( , )where and are integers in the range [ , ]for some integer > in context such as thisit is natural to define an ordering on these keys using the lexicographical (dictionaryconventionwhere ( , ( , if or if and (section this is pair-wise version of the lexicographic comparison functionusually applied to equal-length character strings (and it easily generalizes to tuples of numbers for the radix-sort algorithm sorts sequence of entries with keys that are pairsby applying stable bucket-sort on the sequence twicefirst using one component of the pair as the ordering key and then using the second component but which order is correctshould we first sort on the ' (the first componentand then on the ' (the second component)or should it be the other way aroundbefore we answer 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 componentthen we get the sequence , (( , )( , )( , )( , )( , )( , )( , )( , ))which is not exactly 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 componentthen we 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