it is easy to see that bucket-sort runs in ( ntime and uses ( nspace hencebucket-sort is efficient when the range of values for the keys is small compared to the sequence size nsay (nor ( log nstillits performance deteriorates as grows compared to an important property of the bucket-sort algorithm is that it works correctly even if there are many different elements with the same key indeedwe described it in way that anticipates such occurrences stable sorting when sorting key-value pairsan important issue is how equal keys are handled let (( )(kn- vn- )be sequence of such entries we say that sorting algorithm is stable iffor any two entries (ki vi and ( of such that ki and (ki vi precedes ( in before sorting (that isi )entry (ki vi also precedes entry ( after sorting stability is important for sorting algorithm because applications may want to preserve the initial order of elements with the same key our informal description of bucket-sort in code fragment guarantees stability as long as we ensure that all sequences act as queueswith elements processed and removed from the front of sequence and inserted at the back that iswhen initially placing elements of into bucketswe should process from front to backand add each element to the end of its bucket subsequentlywhen transferring elements from the buckets back to swe should process each [ifrom front to backwith those elements added to the end of 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 (kl)where and are integers in the range [ ]for some integer > in context such as thisit is common to define an order on these keys using the lexicographic (dictionaryconventionwhere ( ( if or if and (see page this is pairwise version of the lexicographic comparison functionwhich can be applied to equal-length character stringsor to tuples of length 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 key when ordering 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 around