TDD on the CPC: counting sort, 256 counts and not one comparison

24/10/2026Z80CPCTDDsorting

The three sorts of the previous posts all do the same thing: they compare bytes, two at a time. The sort of this post compares nothing at all. It is a well-known algorithm, counting sort: we count the bytes, then write them back in order. Simple, but how many NOPs?

The answer takes shape in Z80, one test at a time, and the count of NOPs gets to choose between two copy loops. To finish, the four sorts run on the same inputs, side by side.

The method is that 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 its length (1 to 255), and the routine sorts the array in place, smallest first. It is the contract of the three previous sorts, and the array still stays within one 256-byte page.

A byte takes only 256 values. So we set aside 256 counts, one for each value. We walk through the array once, and each byte adds 1 to its count. Then we walk through the counts in order, from #00 to #FF, and write each value back as many times as we counted it. The array comes out sorted, without a single comparison between two bytes.

Play the animation, or go step by step. The first row is the array, and the arrow shows the byte being counted. The second row shows the counts of the values in the array, and “…” the empty counts between them. The filled box shows the count being read or changed, and the boxes with a coloured outline the bytes already written back. The animation shows the final version of the post: each copy takes 1 off the count, which gets back to zero with the last one. The section on counting down explains why.

The cost changes shape: it has no n² term any more, but two terms, n for counting and writing back, and 256 for the scan of the counts, whatever the size of the array. On a small array, these 256 counts cost a lot. On a large one, they hardly matter. The tests will measure where the line falls.

The table of counts

With 255 bytes at most, a count never goes above 255: one byte is enough. The counts live in a table counts of 256 bytes, aligned on a page. H then points at the table, and L alone picks the count: ld l,a then inc (hl), and the count of the value A goes up by 1.

The table must also go back to zero. We could clear it at the start of each call, but we do otherwise: the table holds zeros on entry, and the routine leaves it at zero on exit. The assembler’s defs 256 creates it full of zeros, and each call leaves it as it found it, which a test checks further on.

The first test

Like insertion sort and bubble sort, counting sort does not need find_min. The code starts from scratch, and the main source includes only the new routine:

 org #4000
 include "counting-sort.asm"

In the tests of this post, HL is #8000 and B the length of the array. So the test tables show only the bytes and the expected result.

An array of one byte is already sorted. The first test only checks that the routine does not touch memory:

// Runs counting_sort on `bytes`, written at ARRAY.
function countingSort(bytes: number[]) {
  return program.run("counting_sort", {
    registers: { hl: ARRAY, b: bytes.length },
    memory: [{ at: ARRAY, bytes }],
  });
}

it("leaves a one-byte array as it is", () => {
  expect(countingSort([0x42])).toLeaveMemoryUnchanged();
});

One byte, then two

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

it("swaps two bytes in the wrong order", () => {
  expect(countingSort([0x42, 0x17]).memory(ARRAY, 2)).toEqual([0x17, 0x42]);
});

AssertionError: expected [ 66, 23 ] to deeply equal [ 23, 66 ]

Vitest shows the bytes in decimal: 66 is #42, and 23 is #17. With the previous sorts, the green code of this step compared two bytes. Here, we count from the second test on. The green code counts each byte, then scans the counts and writes each counted value back, once. It also sets each count back to zero on the way (counting/04-green):

; Sorts in place, smallest first, the array at HL, B bytes long (1 to 255).
; The array stays within one 256-byte page: INC E never carries into D.
; counts must hold zeros on entry, and holds zeros again on exit.
counting_sort:
 ex de,hl       ; DE: the array
 push de
 ld hl,counts
.count:
 ld a,(de)
 ld l,a
 inc (hl)       ; one more copy of this byte
 inc e
 djnz .count
 pop de         ; DE: back to the first byte
.scan:          ; L runs over the counts, up to #FF
 ld a,(hl)
 or a
 jr z,.next
 ld (hl),0      ; the count goes back to zero for the next call
 ld a,l
 ld (de),a
 inc e
.next:
 inc l
 jr nz,.scan
 ret

 align 256
counts:         ; one count for each byte value: L indexes it alone
 defs 256

DE points at the array, HL at the table. The scan stops when inc l wraps round to zero, after the count of #FF. This code has a flaw that the tests do not see yet, and we will come back to it.

Repeated bytes

A value can appear more than once. The next test puts in two pairs (counting/05-red):

it("keeps every copy of a repeated byte", () => {
  expect(countingSort([0x42, 0x17, 0x42, 0x17]).memory(ARRAY, 4)).toEqual([
    0x17, 0x17, 0x42, 0x42,
  ]);
});

AssertionError: expected [ 23, 66, 66, 23 ] to deeply equal [ 23, 23, 66, 66 ]

In hexadecimal, the routine left #17, #42, #42, #17. #17 and #42 are written once each, and the end of the array keeps its old bytes. The count now serves as a length: B takes it, and a loop writes the value B times (counting/06-green):

.scan:          ; L runs over the counts, up to #FF
 ld a,(hl)
 or a
 jr z,.next
 ld b,a         ; B: the copies of this byte to write
 ld (hl),0      ; the count goes back to zero for the next call
 ld a,l
.copy:
 ld (de),a
 inc e
 djnz .copy
.next:
 inc l
 jr nz,.scan
 ret

B is free, since the counting loop left it at zero.

A scan that starts in the wrong place

The next test sorts five mixed bytes (counting/07-red):

it("sorts five bytes in any order", () => {
  expect(countingSort([0x42, 0x30, 0x05, 0x17, 0x99]).memory(ARRAY, 5)).toEqual([
    0x05, 0x17, 0x30, 0x42, 0x99,
  ]);
});

AssertionError: expected [ 153, 48, 5, 23, 153 ] to deeply equal [ 5, 23, 48, 66, 153 ]

In hexadecimal, the routine left #99, #30, #05, #17, #99. Only the first byte changed, and it is #99, because the scan does not start from #00. After the counting loop, L keeps the last byte counted, here #99. So the scan starts at the count of #99, writes #99, then reads empty counts up to #FF and stops. The counts from #05 to #42 were never read.

The flaw had been there since 04-green. The earlier tests passed by luck: in #42, #17 as in #42, #17, #42, #17, the last byte is also the smallest. The scan started from #17, and missed nothing.

The fix takes one instruction. After djnz, B is zero, and ld l,b sets L to #00 for 1 NOP, where ld l,0 costs 2 (counting/08-green):

 pop de         ; DE: back to the first byte
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.scan:          ; L runs over the 256 counts

The two ends of the table

The next test passes as soon as it is written: it is a guard. A guard must prove that it can fail. So we break the routine on purpose, and check that it turns red. This guard aims at the two ends of the table, the counts of #00 and #FF (counting/09-guard):

// #00 and #FF sit in the first and last counts: the scan must read all 256.
it("sorts #FF and #00, the two ends of the counts", () => {
  expect(countingSort([0xff, 0x42, 0x00]).memory(ARRAY, 3)).toEqual([0x00, 0x42, 0xff]);
});

The broken version it aims at stops the scan one count too early. A ld a,l and an inc a before the jr nz,.scan are enough: the loop stops as soon as L reaches #FF, before reading its count. No other test holds #FF, and only this guard fails:

AssertionError: expected [ +0, 66, +0 ] to deeply equal [ +0, 66, 255 ]

Vitest writes zero as +0. In hexadecimal, the guard expected #00, #42, #FF and finds #00, #42, #00: the #FF was never written back.

Bubble sort had a guard for one pair too many, which read the byte after the array. Here, the version that counts one byte too many, with an inc b on entry, passes none of the existing tests. It counts the #00 that follows the array, then writes back one byte too many, and the existing tests are enough to catch it.

A table left clean

The contract promises a table at zero on exit. The next guard checks it: only the array may change (counting/10-guard):

// A count of 2 or more must also go back to zero: the next call counts on top of it.
it("changes only the array, even with repeated bytes", () => {
  expect(countingSort([0x42, 0x17, 0x42, 0x17])).toChangeOnly({ address: ARRAY, length: 4 });
});

The array has repeated bytes because the broken version it aims at puts dec (hl) in place of ld (hl),0. A count of 1 does go back to zero, but a count of 2 stays at 1. The sort stays right, since B keeps the right number of copies, and all the other tests pass. The guard sees what is left over:

Error: Memory changed outside #8000-#8003:
  #4117  #00 -> #01
  #4142  #00 -> #01

The table is at #4100, right after the code of the program. The counts of #17 and #42 stayed at 1 there. The next call would count on top of them, and write one #17 and one #42 too many.

Counting down in the table

Everything is green, and the code can slim down. The copy loop counts with B, then the count is set back to zero. It is simpler to count down in the table itself: dec (hl) reaches zero with the last copy, and the table is clean with nothing more. ld b,a and ld (hl),0 go away (counting/11-refactor):

; Sorts in place, smallest first, the array at HL, B bytes long (1 to 255).
; The array stays within one 256-byte page: INC E never carries into D.
; counts must hold zeros on entry, and holds zeros again on exit.
counting_sort:
 ex de,hl       ; DE: the array
 push de
 ld hl,counts
.count:
 ld a,(de)
 ld l,a
 inc (hl)       ; one more copy of this byte
 inc e
 djnz .count
 pop de         ; DE: back to the first byte
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.scan:          ; L runs over the 256 counts
 ld a,(hl)
 or a
 jr z,.next
 ld a,l
.copy:
 ld (de),a
 inc e
 dec (hl)       ; the count reaches zero with the last copy, ready for the next call
 jr nz,.copy
.next:
 inc l
 jr nz,.scan
 ret

 align 256
counts:         ; one count for each byte value: L indexes it alone
 defs 256

But a copy now costs 9 NOPs instead of 7: dec (hl) and jr nz take 6 NOPs, where djnz took 4. The balance depends on the input, then, and we have to count.

Counting by hand

The count depends on n, the length of the array, and on d, the number of different values it holds. Each loop costs one NOP less on its last turn, when its jump is not taken.

The scan of the 256 counts weighs 2 559 NOPs, whatever happens. The sum gives 2 573 + 20n − d NOPs.

The same count on the djnz loop of 08-green gives 2 573 + 18n + 3d NOPs. The version that counts down wins when d is above n/2. The worst case matters more:

The worst case drops by one NOP a byte, and that is what decided it.

The budgets

The last two tests are budget guards: a number of NOPs not to exceed. First the worst case, equal bytes (counting/12-guard):

// Equal bytes are the slowest input: one count, then n turns of the copy loop.
it.each([2, 16, 255])("sorts %i equal bytes in 20n + 2572 NOPs at most", (n) => {
  const equal = Array.from({ length: n }, () => 0x42);

  expect(countingSort(equal).nops).toBeLessThanOrEqual(20 * n + 2572);
});

The broken version it aims at puts the ld a,l inside the copy loop, after the label. The sort stays right, but each copy costs one NOP more, and each full count one NOP less. On bytes that all differ, each count is 1, and the broken version costs exactly as much as the good one. Equal bytes, on the other hand, make n copies of a single count:

AssertionError: expected 2613 to be less than or equal to 2612
AssertionError: expected 2907 to be less than or equal to 2892
AssertionError: expected 7926 to be less than or equal to 7672

Then sorted and reversed bytes, together (counting/13-guard):

// The order changes nothing: sorted and reversed bytes both mean n counts of 1.
it.each([2, 16, 255])("sorts %i sorted or reversed bytes in 19n + 2573 NOPs at most", (n) => {
  const sorted = Array.from({ length: n }, (_, i) => i);
  const reversed = [...sorted].reverse();

  expect(countingSort(sorted).nops).toBeLessThanOrEqual(19 * n + 2573);
  expect(countingSort(reversed).nops).toBeLessThanOrEqual(19 * n + 2573);
});

For the first time in the series, the order changes nothing. Sorted or reversed, each value has a count of 1, and the routine does exactly the same work. The broken version this guard catches is the djnz loop of 08-green, at 21n + 2 573. It passes the budget of equal bytes, where it is cheaper, and fails here:

AssertionError: expected 2615 to be less than or equal to 2611
AssertionError: expected 2909 to be less than or equal to 2877
AssertionError: expected 7928 to be less than or equal to 7418

Four sorts head to head

Here are the formulas of the four sorts, on the same three inputs:

And for 255 bytes:

The chart shows reversed bytes. At the top, from 2 to 40 bytes, on a linear scale. At the bottom, from 2 to 255 bytes, on a log scale:

On small arrays, counting sort is the slowest, by far: 2 611 NOPs for two bytes, when the other three take fewer than 60. But its line goes up by 19 NOPs a byte, and the parabolas end up crossing it. On reversed bytes, it moves ahead of bubble sort from 18 bytes, then ahead of selection and insertion sort from 21 bytes. At 255 bytes, its worst case, 7 672 NOPs, fits in 38% of a frame of 19 968 NOPs. Against the worst case of each, that is 52 times less than selection and insertion sort, and 72 times less than bubble sort.

Counting sort does not win everywhere, though. On an array that is already sorted, or on equal bytes, bubble sort stays ahead at every size: 3 066 NOPs for 255 bytes, against 7 418. Insertion sort holds out too, up to 185 sorted bytes and 199 equal bytes. Counting sort does not know that the array is already sorted: it pays for its 256 counts at each call.

Conclusion

Counting sort compares nothing, and it gains a linear cost from it, the same for all inputs to within one NOP a byte. The tests found a scan that started in the wrong place, then kept the table clean from one call to the next. The count of NOPs, for its part, chose the copy loop, for one NOP a byte saved on the worst case.

This speed comes with limits:

• 1 to 255 bytes, within one 256-byte page;
• a fixed entry price: 2 559 NOPs to scan the table, and 256 bytes of memory to hold it;
• on a sorted array or on equal bytes, bubble sort stays faster at every size;
• bare bytes only: with a key and its data, the rebuild loses the link between the two, as it knows how many #42s to write, not which ones.

The next post moves on to radix sort, on 16-bit keys. Counting comes back there, in a stable form, as the inner pass.

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 counting branch of the z80-tdd-sorts repository. It starts from main, like the bubble branch. To replay a step:

git checkout counting/01-red
pnpm install
pnpm test

The tests of the sort are in src/counting-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.

Links

• The previous post: bubble sort, the flag or Knuth’s bound
• Insertion sort and selection sort
• The introduction: find_min and TDD on the CPC
• z80-tdd, the test tool
• z80-tdd-sorts, the repository of this post (branch counting)
• RASM, the assembler by Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), the table of durations in NOPs