Blog

TDD on the CPC: radix sort, two counting passes for 16-bit keys

24/10/2026Z80CPCTDDsorting

The counting sort of the previous post moves nothing: it counts the bytes, then writes them back. It knows how many #42 to write, not which ones. With bytes alone, this is no problem. But how do we sort 16-bit keys, when one count for each possible key would not fit in memory?

Radix sort gets there with two counting passes, one for each byte of the key. The tests will guide its writing in Z80, one by one, then the count of NOPs will tell what these two passes cost against counting sort alone.

The method is the one of the post on find_min, to read first if TDD is new to you.

What the routine does

HL points at the array, B holds the number of keys (1 to 255), and the routine sorts the keys in place, smallest first. Each key takes two bytes, the low byte first. DE points at a buffer of 2n bytes, given by the caller, apart from the array. The sort uses it as scratch space, and what the buffer holds on exit does not matter.

Radix sort sorts the keys one digit at a time. Here, a digit is a byte, and a 16-bit key has two of them. We sort on the low byte first, then on the high byte. Each pass is a counting sort, but of another form than in the previous post:

  1. We count the digits, one count for each value, as before.
  2. Each count becomes a slot of the destination: the slot of the first key with its digit. It is the sum of the counts of all the smaller digits.
  3. We read the keys in order, and each one goes to the slot of its digit, which moves on by one slot.

This counting sort moves the keys. So it needs a destination: the first pass goes from the array to the buffer, the second comes back from the buffer to the array.

Play the animation, or go step by step. The first row is the array, the last one the buffer, and the arrow shows the key being read. Between them, the table shows the counts of the digits in the keys, and “…” the empty counts. After the sums, a count becomes a slot, written →2: the slot where the next key with this digit will go. Slots are numbered from 0. A filled background marks the count being read or changed and, during the moves, the slot the key goes to. A coloured outline marks the keys already written by the pass.

On the keys #0201 #0142 #0117 #0102, the pass on the low byte writes #0201 #0102 #0117 #0142 into the buffer. The pass on the high byte puts the three keys in #01 before #0201, without changing their order: the sorted array is #0102 #0117 #0142 #0201.

Everything rests on the end of pass 2. The three keys in #01 have the same high byte, and they come out in the order pass 1 left them in. We say the pass is stable: two keys with the same digit keep their order. This counting sort is stable with nothing more, because the keys with the same digit fill their slots in reading order. Without this stability, pass 2 would undo the work of pass 1.

On bytes alone, radix sort brings nothing: a byte has only one digit in base 256, and a radix sort in one pass is counting sort.

Two aligned tables

Counting sort kept its counts in a table counts of 256 bytes, aligned on a page, and L alone picked the count. Radix sort keeps this table: with 255 keys at most, a count still fits in one byte.

But a slot of the destination is a 16-bit address. So the sums put the low byte of the address in counts, in place of the count, and the high byte in a second table, slots_hi, the page just above. An inc h goes from one to the other.

The table can no longer stay clean from one call to the next, as in counting sort: after a pass, it holds addresses. So each pass starts by clearing it.

The first test

Radix sort does not need the routines of the previous posts. The main source includes only the new routine:

 org #4000
 include "radix-sort.asm"

In the tests of this post, HL is #8000, DE is #8200, and B the number of keys. So the test tables show only the keys and the expected result.

A single key is already sorted. The first test checks that it stays in place:

Keys Expected
#1234 #1234 in memory
The test in TypeScript

The function radixSort writes each key as two bytes, the low byte first, then calls the routine. The function keysAfter reads the keys back after the call.

// Runs radix_sort on the 16-bit `keys`, written little-endian at ARRAY.
function radixSort(keys: number[]) {
  const bytes = keys.flatMap((key) => [key & 0xff, key >> 8]);

  return program.run("radix_sort", {
    registers: { hl: ARRAY, b: keys.length, de: BUFFER },
    memory: [{ at: ARRAY, bytes }],
  });
}

// Reads back the `count` 16-bit keys at ARRAY after a Run.
function keysAfter(run: ReturnType<typeof radixSort>, count: number) {
  const bytes = run.memory(ARRAY, 2 * count);

  return Array.from({ length: count }, (_, i) => bytes[2 * i] | (bytes[2 * i + 1] << 8));
}

it("leaves a one-key array as it is", () => {
  expect(keysAfter(radixSort([0x1234]), 1)).toEqual([0x1234]);
});

One key, then two

The first steps follow those of the previous sorts. The one-key test fails for lack of a label (radix/01-red), and a plain ret makes it pass (radix/02-green). Two keys in the wrong order expose this cheat. They differ only in the low byte (radix/03-red):

Keys Expected
#0142, #0117 #0117, #0142 in memory
The test in TypeScript 
it("sorts two keys by their low byte", () => {
  expect(keysAfter(radixSort([0x0142, 0x0117]), 2)).toEqual([0x0117, 0x0142]);
});
AssertionError: expected [ 322, 279 ] to deeply equal [ 279, 322 ]

Vitest shows the keys in decimal: 322 is #0142, and 279 is #0117.

One pass on the low byte

The green code makes a full pass on the low byte, from the array to the buffer. Then an ldir copies the buffer back to the array (radix/04-green):

; Sorts in place, smallest first, the B 16-bit keys at HL (1 to 255), little-endian.
; DE: a buffer of 2B bytes, apart from the array. Its contents on exit are free.
; Each pass is a stable counting sort on one byte of the keys.
radix_sort:
 push hl        ; the array
 push bc        ; B: the key count
 push de        ; the buffer
 ex de,hl       ; DE: the array
 ld hl,counts
 xor a
.clear:
 ld (hl),a
 inc l
 jr nz,.clear
.count:         ; L: back at #00
 ld a,(de)
 ld l,a
 inc (hl)       ; one more key with this low byte
 inc de
 inc de
 djnz .count
 pop de         ; DE: the buffer, the slot of the first key
 push de
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.sums:          ; each count becomes the slot of the first key with its byte
 ld c,(hl)      ; BC: the count, as B is zero
 ld (hl),e
 inc h
 ld (hl),d
 dec h
 ex de,hl
 add hl,bc      ; two bytes for each key
 add hl,bc
 ex de,hl
 inc l
 jr nz,.sums
 pop de         ; DE: the buffer
 pop bc
 pop hl         ; HL: the array
 push hl
 push de
 ld c,b
 ld b,0
 sla c
 rl b           ; BC: 2B, the bytes to move
 push bc
.move:          ; LDI counts BC down: JP PE loops until the last byte
 ld a,(hl)      ; A: the low byte, the digit of this pass
 push hl
 ld l,a
 ld h,counts >> 8
 ld e,(hl)
 inc h
 ld d,(hl)      ; DE: the slot of this key
 pop hl
 ldi
 ldi
 push hl
 ld l,a
 ld h,counts >> 8 ; LD, not DEC H: the P/V flag of LDI must live until JP PE
 ld (hl),e      ; the next key with this digit goes in the next slot
 ld h,slots_hi >> 8
 ld (hl),d
 pop hl
 jp pe,.move
 pop bc         ; BC: 2B
 pop hl         ; HL: the buffer
 pop de         ; DE: the array
 ldir           ; the sorted keys go back to the array
 ret

 align 256
counts:         ; for each byte value: its count, then the low byte of its next slot
 defs 256
slots_hi:       ; for each byte value: the high byte of its next slot, one page above
 defs 256

The three steps of the animation are there, after the table is cleared:

ldi is also the loop counter. It decrements BC, and its P/V flag drops to zero when BC reaches zero. So BC starts at 2n, two bytes for each key, and jp pe loops until the last one. Between the last ldi and the jp pe, nothing may touch P/V. This is why the routine uses ld h,counts >> 8 in place of a dec h: dec h changes P/V, and the loop would stop at the whim of the addresses.

The high byte

The next test takes two keys that differ only in the high byte (radix/05-red):

Keys Expected
#0201, #0102 #0102, #0201 in memory
The test in TypeScript 
it("sorts two keys by their high byte", () => {
  expect(keysAfter(radixSort([0x0201, 0x0102]), 2)).toEqual([0x0102, 0x0201]);
});
AssertionError: expected [ 513, 258 ] to deeply equal [ 258, 513 ]

513 is #0201, and 258 is #0102. On the low byte, #0201 comes before #0102, and pass 1 leaves the array as it is. The green code adds a second pass, on the high byte, from the buffer back to the array. It is a copy of the first, with numbered labels (radix/06-green). Pass 2 writes straight into the array, and the ldir goes away. It reads the digit one byte further on: through an inc de before the counting loop, and in the move, like this:

.move2:         ; LDI counts BC down: JP PE loops until the last byte
 inc hl
 ld a,(hl)      ; A: the high byte, the digit of this pass
 dec hl

The rest of pass 2 does not change by a single instruction.

This green code also changes the role of the earlier test. #0142 and #0117 have the same high byte, #01. So pass 2 must leave them in the order of pass 1. The low-byte test now checks the stability of pass 2, with no separate test: a pass 2 that reads the keys from the end back to the start makes it fail.

The stability of pass 1, for its part, does not show with keys alone. Two keys with the same low byte and the same high byte are the same key, and their order changes nothing in the result.

One pass, two calls

Everything is green, and the code holds two passes that are almost the same. They differ only in the byte that serves as the digit, the first or the second of the key. What remains is to write just one.

Three ideas come up:

We take the third: the buffer gets the keys the other way round, the high byte first. Pass 2 then reads the digit in the first byte, like pass 1, and puts each key back the right way round (radix/07-refactor):

; Sorts in place, smallest first, the B 16-bit keys at HL (1 to 255), little-endian.
; DE: a buffer of 2B bytes, apart from the array. Its contents on exit are free.
radix_sort:
 push de        ; the buffer
 push bc
 push hl        ; the array
 call .pass     ; the low byte, from the array to the buffer
 pop de         ; DE: the array
 pop bc         ; B: the key count
 pop hl         ; HL: the buffer
 call .pass     ; the high byte, from the buffer back to the array
 ret

; A stable counting sort of the B keys at HL into DE, on the first byte of each key.
; Each key goes out with its two bytes swapped: the buffer holds the keys big-endian,
; so the second pass reads the high byte first, and swaps the keys back.
.pass:
 push hl        ; the source
 push bc        ; B: the key count
 push de        ; the destination
 ex de,hl       ; DE: the source
 ld hl,counts
 xor a
.clear:
 ld (hl),a
 inc l
 jr nz,.clear
.count:         ; L: back at #00
 ld a,(de)
 ld l,a
 inc (hl)       ; one more key with this byte
 inc de
 inc de
 djnz .count
 pop de         ; DE: the destination, the slot of the first key
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.sums:          ; each count becomes the slot of the first key with its byte
 ld c,(hl)      ; BC: the count, as B is zero
 ld (hl),e
 inc h
 ld (hl),d
 dec h
 ex de,hl
 add hl,bc      ; two bytes for each key
 add hl,bc
 ex de,hl
 inc l
 jr nz,.sums
 pop bc
 pop hl         ; HL: the source
 ld c,b
 ld b,0         ; BC: the key count
.move:          ; LDI counts BC down: JP PE loops until the last key
 ld a,(hl)      ; A: the first byte, the digit of this pass
 push hl
 ld l,a
 ld h,counts >> 8
 ld e,(hl)
 inc h
 ld d,(hl)      ; DE: the slot of this key
 pop hl
 inc hl
 ldi            ; the second byte goes first
 ld (de),a      ; then the digit
 inc de
 push hl
 ld l,a
 ld h,counts >> 8 ; LD, not DEC H: the P/V flag of LDI must live until JP PE
 ld (hl),e      ; the next key with this digit goes in the next slot
 ld h,slots_hi >> 8
 ld (hl),d
 pop hl
 jp pe,.move
 ret

 align 256
counts:         ; for each byte value: its count, then the low byte of its next slot
 defs 256
slots_hi:       ; for each byte value: the high byte of its next slot, one page above
 defs 256

The digit is already in A. So the pass copies the second byte with ldi, then writes A after it. Only one ldi is left for each key: BC starts at n, and the sla c / rl b goes away. The animation at the top, for its part, shows the keys of the buffer the right way round: it follows the algorithm, not the order of the bytes.

The routine has no parameter and no code that modifies itself, and the source shrinks by half. The gain in NOPs is thinner. Pass 1 costs 1 NOP more per key, pass 2 3 NOPs less. The fixed part takes 6 NOPs more: the two call and their ret cost 16, the sla c / rl b of both passes and one inc de give back 10. The two versions cost the same at three keys, and the refactor pulls ahead from four.

The two ends of the keys

The next tests pass as soon as they are written: they are guards. A guard must prove that it can fail. So we break the routine on purpose, and check that it turns red. The first one aims at the two ends of the keys, #0000 and #FFFF (radix/08-guard):

Keys Expected
#FFFF, #0000 #0000, #FFFF in memory
The test in TypeScript 
it("sorts #FFFF and #0000, the two ends of the keys", () => {
  expect(keysAfter(radixSort([0xffff, 0x0000]), 2)).toEqual([0x0000, 0xffff]);
});

The broken version it aims at stops .sums one count too early. A ld a,l and an inc a before the jr nz,.sums are enough: the loop stops as soon as L reaches #FF, before handling its count. The count of #FF never becomes a slot. So the key #FFFF goes to address #0001: the low byte of its slot is still its count, 1, and slots_hi holds zero. No other test has a #FF digit, and only this guard fails:

AssertionError: expected [ +0, +0 ] to deeply equal [ +0, 65535 ]

Vitest writes zero as +0, and 65535 is #FFFF. The guard expected #0000, #FFFF and finds #0000, #0000.

Four ranges, not one more

The contract gives the sort four areas of memory: the array, the buffer and the two tables. The next guard checks that it writes nowhere else, out of its stack (radix/09-guard):

Keys Expected
#0142, #FFFF, #0117, #0000, #0142 nothing changed outside the array, the buffer, counts and slots_hi
The test in TypeScript

The toChangeOnly matcher of z80-tdd 0.1.0 takes only one range. So the test filters the memory changes itself.

// The Memory changes of a Run that lie in none of the `ranges`: toChangeOnly takes one range.
function changesOutside(run: ReturnType<typeof radixSort>, ranges: MemoryRange[]) {
  return run.memoryChanges.filter(({ address }) =>
    ranges.every((range) => ((address - range.address) & 0xffff) >= range.length),
  );
}

// Out of its stack, which no test sees, radix_sort may write only these four ranges.
it("changes only the array, the buffer and its two tables", () => {
  const keys = [0x0142, 0xffff, 0x0117, 0x0000, 0x0142];
  const run = radixSort(keys);

  expect(
    changesOutside(run, [
      { address: ARRAY, length: 2 * keys.length },
      { address: BUFFER, length: 2 * keys.length },
      program.range("counts", 256),
      program.range("slots_hi", 256),
    ]),
  ).toEqual([]);
});

The broken version it aims at keeps the key count in a variable, instead of the stack: a defb placed just after the ret of radix_sort, before .pass. The sort stays right, and only this guard sees the extra byte:

- Expected
+ Received

- []
+ [
+   {
+     "address": 16403,
+     "after": 5,
+     "before": 0,
+   },
+ ]

16403 is #4013, the address of this variable. It gets 5 there, the key count.

Counting by hand

The last guard is about time. We count first, with Madram’s table. Each loop costs one NOP less on its last turn, when its jump is not taken. jp pe is the exception: it costs 3 NOPs, whether it jumps or not.

Part NOPs
Each key, in each pass. Counting: ld a,(de) 2, ld l,a 1, inc (hl) 3, two inc de 4, djnz 4, that is 14. Moving, from ld a,(hl) to jp pe: 47 61n per pass
Clearing counts: ld (hl),a 2, inc l 1, jr nz 3, for each of the 256 values 256 × 6 − 1 = 1 535 per pass
Sums: 20 NOPs for each of the 256 values 256 × 20 − 1 = 5 119 per pass
Rest of the pass: push, pop, setting up the registers, ret; the last djnz 1 less 32 per pass
radix_sort, around the two calls: three push, two call, three pop, ret 34

So one pass costs 61n + 6 686 NOPs, and the two passes with their call 122n + 13 406 NOPs.

This total does not depend on the keys. No jump of the routine depends on their value: each loop runs n times or 256 times. Sorted, reversed, equal or random, an array of n keys always costs the same number of NOPs.

The budget

So one budget guard is enough, on three inputs at once (radix/10-guard):

Keys Expected
n keys equal to #4242, n rising keys (#0000, #0101, #0202…), then the same reversed, for n = 2, 16 and 255 122n + 13 406 NOPs at most: 13 650, 15 358 and 44 516
The test in TypeScript 
// No branch of radix_sort depends on the keys: every input of n keys costs the same.
it.each([2, 16, 255])("sorts %i keys in 122n + 13406 NOPs at most, in any order", (n) => {
  const equal = Array.from({ length: n }, () => 0x4242);
  const sorted = Array.from({ length: n }, (_, i) => i * 0x0101);
  const reversed = [...sorted].reverse();

  for (const keys of [equal, sorted, reversed]) {
    expect(radixSort(keys).nops).toBeLessThanOrEqual(122 * n + 13406);
  }
});

The broken version it catches is the code of 06-green, before the refactor. It costs 124n + 13 400 NOPs: 6 NOPs less in the fixed part, 2 more per key. At two keys, it still passes, with 13 648 NOPs for a budget of 13 650. It fails at 16 and 255 keys:

AssertionError: expected 15384 to be less than or equal to 15358
AssertionError: expected 45020 to be less than or equal to 44516

Radix sort and counting sort

The counting sort of the previous post cost from 19n + 2 573 to 20n + 2 572 NOPs. Radix sort costs 122n + 13 406 NOPs. It is dearer on both terms, but it does not sort the same thing.

The fixed part is five times heavier. Radix sort makes two passes, and each one walks through the 256 values twice. It clears counts, which counting sort left clean. And a sum costs 20 NOPs per value, where the scan of counting sort cost 10. Over the two passes, the sums weigh 10 238 NOPs, and the clears 3 070.

Per key, the gap is six times. Counting sort added 1 to a count, then wrote a byte back. Radix sort counts and moves a two-byte key, twice. The move is costly: it reads the slot from two tables, copies the key, then stores the next slot.

At 255 keys, radix sort takes 44 516 NOPs, a little more than two frames of 19 968 NOPs. Counting sort sorted 255 bytes in 7 672 NOPs at worst. But counting sort cannot sort 16-bit keys: it would need 65 536 counts, that is 64 KB, as much as all the memory of a 464. Radix sort makes do with 512 bytes of tables, and a buffer of 2n bytes.

Conclusion

Radix sort reuses counting sort, in a stable form, as its inner pass. It moves the keys, which counting sort could not do, and two passes are enough for 16-bit keys, at a cost of 122n + 13 406 NOPs that does not depend on the input. On the way, the low-byte test changed its role to keep the second pass stable, and a byte swap made the two passes into one routine.

The routine also comes with constraints:

The next post leaves numbers for strings, with a routine that compares two names in the firmware format.

Trying it yourself

You need Node.js 24 or later, pnpm, and RASM v3.3.1 on the PATH. The steps of this post are on the radix branch of the z80-tdd-sorts repository. It starts from main, like the counting branch. To replay a step:

git checkout radix/01-red
pnpm install
pnpm test

The tests of the sort are in src/radix-sort.test.ts. To install z80-tdd in a project of your own, see the Trying it yourself section of the post on find_min.