Placing Items Front to Back in a Radix Sort's Counting Pass

A radix sort whose counting pass walks the input from the first item while it fills each digit's last free position returns its keys in the wrong order, with no error. This card shows the symptom, the one loop that causes it, and the fix.

The symptom is a radix sort that sorts some inputs and scrambles others. Keys with all different digits come out right, so a quick test with 3 1 2 passes. Keys that share a digit come out in an order that looks almost random.

The trigger is the placing loop. After the prefix sums, each digit's counter holds the position just past the end of that digit's block, and the loop takes one from the counter and writes the item there, filling each block from its end towards its start. Walking the input from the last item fills each block with its last item first, which keeps equal digits in input order. Walking from the first item fills each block with its first item last, which reverses them.

A run sorted 13 4 10 7 14 3 10 both ways and printed the array after each pass.

The mechanism is in the second row. The ones pass reversed each group that shares a ones digit, so 3 came before 13 and 14 before 4; that pass alone still sorts by its digit. The damage shows in the tens pass. It groups 3, 4 and 7 by their tens digit, 0, and relies on the ones pass having put them in order, but it reverses them too, and every group comes out backwards: 7 4 3, then 14 13 10 10. Each pass is a correct sort by its own digit and an unstable one, and radix sort needs stable passes, because the tens pass breaks ties only by leaving the earlier order alone.

The cost is wrong output and no failure: no index goes out of range, every item appears once, and a test on keys with distinct digits passes. The same reversal happens in a counting sort of records, where two records with the same key swap places.

The remedy is to walk the input from the last item, for value in reversed(items), as every listing in this topic does.