Editing Radix sort (section)

== Digit order ==

Radix sorts can be implemented to start at either the [[most significant digit]] (MSD) or [[least significant digit]] (LSD). For example, with '''1234''', one could start with 1 (MSD) or 4 (LSD).

LSD radix sorts typically use the following sorting order: short keys come before longer keys, and then keys of the same length are sorted [[lexicographically]]. This coincides with the normal order of integer representations, like the sequence '''[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]'''. LSD sorts are generally [[stable sort]]s.

MSD radix sorts are most suitable for sorting strings or fixed-length integer representations. A sequence like '''[b, c, e, d, f, g, ba]''' would be sorted as '''[b, ba, c, d, e, f, g]'''. If lexicographic ordering is used to sort variable-length integers in base 10, then numbers from 1 to 10 would be output as '''[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]''', as if the shorter keys were left-justified and padded on the right with blank characters to make the shorter keys as long as the longest key. MSD sorts are not necessarily stable if the original ordering of duplicate keys must always be maintained.

Other than the traversal order, MSD and LSD sorts differ in their handling of variable length input.
LSD sorts can group by length, radix sort each group, then concatenate the groups in size order. MSD sorts must effectively 'extend' all shorter keys to the size of the largest key and sort them accordingly, which can be more complicated than the grouping required by LSD.

However, MSD sorts are more amenable to subdivision and recursion. Each bucket created by an MSD step can itself be radix sorted using the next most significant digit, without reference to any other buckets created in the previous step. Once the last digit is reached, concatenating the buckets is all that is required to complete the sort.