Decomposing keys into positions
Integers can be split into bits or bytes, and strings into character positions. Radix R describes the possible values at one position, such as 256 for a byte. Distribution by these categories replaces repeated comparisons of complete keys.
Position ordering must match the intended total order. Signed integers require special treatment of the most significant byte so negative values precede nonnegative values. Raw unsigned byte order does not automatically implement signed numeric order.
References: [1]
LSD sorting relies on stable passes
LSD sorting begins with the least significant position and moves toward more significant ones. Each pass must preserve prior order among records equal at the current position, retaining lower-position information as a tie-break. Stable counting distribution supplies that property.
For fixed-width W keys with radix R, a common implementation makes W passes of O(n+R), totaling O(W(n+R)). Calling this linear in n assumes fixed W and R; reading growing keys still costs work.
References: [1]
MSD sorting refines shared prefixes
MSD sorting distributes by the most significant position, then processes the next position within each group. String implementations can use an end sentinel so a shorter prefix precedes its extensions and completed strings are not recursively extended.
Radix choice, buffering and small-group optimizations change resource use. Encoded character order is not universal linguistic order; case and Unicode conventions need an explicit key policy. The algorithm organizes a representation rather than choosing the application’s comparison semantics.