Why did a radix sort place -5 after 1000000 in its output once the keys included signed values?

## Reading the symptom precisely The report is "`-5` sorted after `1000000`". Before theorising, look at the whole output: the giveaway is that it is not randomly wrong. It reads as every non-negative value in correct ascending order, followed by every negative value — usually also in correct ascending order among themselves. One contiguous block is in the wrong place. That signature immediately rules out a stability bug (which scrambles low digits) and points at how the most significant digit is being interpreted. ## The mechanism Radix passes do not know what a key *means*. They extract a digit and place the record in the bucket with that digit's index, and at the end of a pass buckets are concatenated in index order: bucket 0, then 1, and so on up to `k-1`. Correctness therefore rests on an assumption: **larger digit value must mean later in the desired order**. For keys stored in a signed `w`-bit representation, negative values carry a set top bit. That bit sits in the digit examined by the last pass, so every negative key's final-pass digit falls in the upper half of the digit range while every non-negative key's falls in the lower half. Concatenating buckets in ascending index order then puts the entire negative block last. The assumption "larger digit value means later" is violated for exactly one bit of the key, and it happens to be the bit the last pass depends on most. Note what is **not** broken: within the negatives, ordering is right, because for two negative values the remaining digits still increase in the same direction as the values. The bug is a block placement, not a scramble — which is why a test suite with only non-negative data passes cleanly and the defect surfaces the first time real data contains a refund, an adjustment, or an offset before an epoch. ## Fix one: bias the keys Add `2^(w-1)` to every key and interpret the result in the unsigned domain. This maps the smallest representable negative value to 0 and the largest positive to the top of the unsigned range, preserving order exactly. Sort as usual on the biased values, then subtract the bias when writing results back. Done naively this is two extra full passes over the data. Done well it costs nothing measurable: fold the bias into digit extraction so the top-digit computation adds it on the fly, leaving the stored records untouched. That keeps the sort non-destructive, which matters when the records are shared or the sort may be aborted. ## Fix two: rotate the final pass's bucket order Leave the keys alone and change the concatenation order of the **last** pass only: emit buckets `k/2 .. k-1` first, then buckets `0 .. k/2-1`. This puts the negative block ahead of the non-negatives while leaving each block internally ordered, which is precisely the correction needed. It is the cheapest fix — one changed loop bound in one pass — and the most dangerous to maintain, because it is a special case that lives in one place and looks like a bug to the next reader. If you take it, the comment above it must say why. Applying the rotation to *every* pass instead of the last is a classic follow-on defect: the lower digits have no sign meaning, so rotating them corrupts the order outright. ## The adjacent trap: fractional keys Do not assume the same fix generalises. Standard floating-point layouts also put a sign bit on top, but negative values additionally run in **decreasing** magnitude order as raw patterns, so a bias alone leaves the negatives internally reversed. The known transform inverts all bits of negative keys and only the sign bit of non-negative ones, producing an order-preserving unsigned image. The interview-safe answer is to say the signed-integer fix does not transfer unchanged, and that fractional keys need their own order-preserving transform plus tests around zero and the special values. ## Testing the fix The reason this defect ships is that the test data has no negatives. Pin it with a fixture that straddles zero deliberately: the most negative representable value, a small negative, negative and positive zero-adjacent values, a small positive, and the largest representative positive — plus duplicates spanning the sign boundary to confirm stability survives the transform. Compare against a reference sort on the same input rather than eyeballing the output. If the bias is folded into digit extraction, add a case asserting the input array is unmodified when the sort is abandoned midway. ## Why interviewers like this one It separates candidates who have run a digit sort on real data from those who have only read the pseudocode. The reasoning chain is short but requires holding two ideas at once: buckets are concatenated in ascending index order, and the raw pattern order of signed keys does not match their numeric order. Getting there, naming both fixes, and flagging that fractional keys need a different treatment is a complete senior answer.