Blog

TDD on the CPC: insertion sort, four versions to the NOP

24/10/2026Z80CPCTDDsorting

The selection sort of the previous post pays no attention to the order of the bytes: even on an array already sorted, it looks for the minimum on every pass. Insertion sort, on the other hand, makes use of the order it finds. But what does it cost when there is none?

To find out, we write it in Z80, one test at a time, try four ways to shift the bytes, measured to the NOP, and end by setting the two sorts against each other.

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 selection_sort, and the array still stays within one 256-byte page.

Insertion sort is the card player’s sort: we pick up the cards one by one, and slide each one into its place among those already in hand. The array splits in two: on the left, a sorted run, on the right, the bytes that remain. At the start, the sorted run holds only the first byte. At each pass, we take the byte that follows it: the key. While the byte on the left of the key is larger than the key, that byte moves one place right. Then the key is written into the freed place.

Play the animation, or go step by step: the boxes with a coloured outline form the sorted run, the filled box shows the key, and the arrow the byte compared with the key. The Z80 keeps the key in A during the shifts, and writes it only at the end. The animation already shows it in the place where it will be written.

On the array #42 #30 #05 #17 #99, the key #30 moves in front of #42. The key #05 moves in front of #42 and #30. The key #17 moves in front of #42 and #30, and stops after #05. The key #99 stays in its place. The sorted array is #05 #17 #30 #42 #99.

On an array already sorted, each key stops at once: one comparison per byte, and that is all. On a reversed array, each key travels across the whole sorted run. The best and the worst case are easy to guess, and the tests will measure them.

The first test

Insertion sort does not need find_min, so the code starts from scratch, and the main source includes only the new routine:

 org #4000
 include "insertion-sort.asm"

In the tests of this post, HL is #8000 and B the length of the array, except in one test, which says so. The test tables therefore only show the bytes and the expected result. They are the same bytes as for selection_sort, to compare the two sorts at the end.

A one-byte array is already sorted. The first test only checks that the routine leaves the memory alone:

Bytes Expected
#42 the memory unchanged
The test in TypeScript

The insertionSort function writes the bytes at #8000, sets HL and B, then calls the routine, like selectionSort in the previous post.

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

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

One byte, then two

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

Bytes Expected
#42, #17 #17, #42 in memory
The test in TypeScript 
it("swaps two bytes in the wrong order", () => {
  expect(insertionSort([0x42, 0x17]).memory(ARRAY, 2)).toEqual([0x17, 0x42]);
});

The plain ret leaves the two bytes as they are:

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

Vitest shows the bytes in decimal: 66 is #42, and 23 is #17. The green code already differs from the selection one. The key is the second byte, and we compare it with the byte before it (insertion/04-green):

insertion_sort:
 dec b
 ret z
 inc l
 ld a,(hl)      ; the key: the byte to insert
 dec l
 cp (hl)
 ret nc         ; the key is not below the byte before it
 ld c,(hl)      ; move that byte one place right, and the key into its place
 ld (hl),a
 inc l
 ld (hl),c
 ret

A single key

The next test puts a key right in front of a run already sorted (insertion/05-red):

Bytes Expected
#17, #30, #42, #05 #05, #17, #30, #42 in memory
The test in TypeScript 
it("moves the last byte to the front of a sorted run", () => {
  expect(insertionSort([0x17, 0x30, 0x42, 0x05]).memory(ARRAY, 4)).toEqual([
    0x05, 0x17, 0x30, 0x42,
  ]);
});

The two-byte version does not see the last key:

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

In hexadecimal, the routine left #17, #30, #42, #05, because it only looks at the first two bytes. For this test, one key is enough, the last one, which steps back towards the start of the array, still without an outer loop (insertion/06-green):

insertion_sort:
 dec b
 ret z
 ld a,l
 add a,b
 ld l,a         ; HL: the last byte
 ld a,(hl)      ; the key: the byte to insert
.shift:
 dec l
 cp (hl)
 jr nc,.place   ; the key is not below this byte
 ld c,(hl)      ; move this byte one place right
 inc l
 ld (hl),c
 dec l
 jr .shift
.place:
 inc l
 ld (hl),a
 ret

This loop has no bound: it stops on the first byte that is not larger than the key. Nothing makes it stop at the start of the array, and we will come back to that later.

The outer loop

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

Bytes Expected
#42, #30, #05, #17, #99 #05, #17, #30, #42, #99 in memory
The test in TypeScript 
it("sorts five bytes in any order", () => {
  expect(insertionSort([0x42, 0x30, 0x05, 0x17, 0x99]).memory(ARRAY, 5)).toEqual([
    0x05, 0x17, 0x30, 0x42, 0x99,
  ]);
});

With a single key, the routine fails on this array:

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

In hexadecimal, the routine left #42, #30, #05, #17, #99, since the last key, #99, was already in its place. The outer loop now inserts each byte in turn. E keeps the position of the key, so that the next pass starts from there (insertion/08-green):

insertion_sort:
 dec b          ; one pass for each byte but the first
 ret z
.next:
 inc l          ; HL: the next byte to insert
 ld e,l         ; the next pass starts from there
 ld a,(hl)      ; the key: the byte to insert
.shift:
 dec l
 cp (hl)
 jr nc,.place   ; the key is not below this byte
 ld c,(hl)      ; move this byte one place right
 inc l
 ld (hl),c
 dec l
 jr .shift
.place:
 inc l
 ld (hl),a
 ld l,e
 djnz .next
 ret

All the tests are green, but the inner loop still has no bound.

The wall before the array

When the key is smaller than every byte of the sorted run, it moves past the first byte, and the loop goes on reading before the array. To prove it, a larger byte, #FF, is enough there: the unbounded code will shift it into the array.

The first attempt put the array at #8000 and the #FF at #7FFF. The test passed when it should have failed, because dec l does not touch H: from #8000, it does not step back to #7FFF, but to #80FF, at the end of the same page. And the fresh memory of z80-tdd is #00 everywhere, so this zero, smaller than any key, stops the loop. Here again, a test passed by luck, as in the post on selection sort.

So the test puts the array one byte further, at #8001, right after the #FF (insertion/09-red). It is the only test where HL is not #8000:

Bytes Expected
#FF at #8000, then #42, #30, #05, #17, #99 at #8001 (HL = #8001, B = 5) #05, #17, #30, #42, #99 at #8001, and nothing changed outside #8001-#8005
The test in TypeScript

toChangeOnly checks that the routine writes only between #8001 and #8005.

it("ignores a larger byte right before the array", () => {
  // Fresh memory holds #00 next to ARRAY. The array starts one byte into the
  // page, after the #FF, so a step back by DEC L or DEC HL reads the #FF.
  const run = program.run("insertion_sort", {
    registers: { hl: ARRAY + 1, b: 5 },
    memory: [{ at: ARRAY, bytes: [0xff, 0x42, 0x30, 0x05, 0x17, 0x99] }],
  });

  expect(run).toChangeOnly({ address: ARRAY + 1, length: 5 });
  expect(run.memory(ARRAY + 1, 5)).toEqual([0x05, 0x17, 0x30, 0x42, 0x99]);
});

This time, it fails for the right reason. From the first pass, the key #30 pushes the #FF into the array, and takes its place, outside the array. On the next pass, the key #05 drives it out:

Error: Memory changed outside #8001-#8005:
  #8000  #FF -> #05

The simplest bound is a counter. D counts the bytes of the sorted run, and E gets a copy of it on each pass: the key cannot move past more than E bytes. As E is taken, the position of the key goes on the stack (insertion/10-green):

insertion_sort:
 dec b          ; one pass for each byte but the first
 ret z
 ld d,0
.next:
 inc d          ; D: the bytes of the sorted run
 inc l          ; HL: the next byte to insert
 push hl        ; the next pass starts from there
 ld e,d         ; E: the bytes the key can still move past
 ld a,(hl)      ; the key: the byte to insert
.shift:
 dec l
 cp (hl)
 jr nc,.place   ; the key is not below this byte
 ld c,(hl)      ; move this byte one place right
 inc l
 ld (hl),c
 dec l
 dec e
 jr nz,.shift
 dec l          ; the key goes first: .place steps back onto the first byte
.place:
 inc l
 ld (hl),a
 pop hl
 djnz .next
 ret

The dec l after the loop is a small trick: .place moves one byte forward before writing, so we step back one more byte when the key goes first.

Four ways to shift

Everything is green, and the routine is correct, but nothing says yet that it is fast. Before setting any budget, we therefore try three other inner loops:

z80-tdd measured the four versions on sorted bytes and on reversed bytes. For each one, counting the NOPs gives an exact formula:

Version sorted bytes reversed bytes
E counter (10-green) 25n − 18 7.5n² + 11.5n − 12
sentinel (Algorithms in C) 37n − 26 7n² + 13n − 9
exchanges (Algorithms, 4th ed.) 22n − 15 8.5n² + 6.5n − 8
LDD 33n − 26 6n² + 22n − 21

The sentinel formulas hold from 3 bytes up. No version wins everywhere:

LDD wins the worst case, and on a sorted array it loses only 8 NOPs per pass against the E counter. It is the one the routine keeps. The refactor replaces the inner loop without touching a single test (insertion/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 keeps D on the page of H.
insertion_sort:
 dec b          ; one pass for each byte but the first
 ret z
 ld c,0
.next:
 inc c          ; C: the bytes of the sorted run
 push bc
 ld d,h         ; DE: the next byte to insert, then the hole it leaves
 ld e,l
 inc e
 push de        ; the next pass starts from there
 ld a,(de)      ; the key: the byte to insert
 ld b,0         ; BC: the bytes the key can still move past
.shift:
 cp (hl)        ; HL: the byte before the hole
 jr nc,.place   ; the key is not below this byte
 ldd            ; move this byte into the hole; P/V: BC is not 0
 jp pe,.shift
.place:
 ld (de),a
 pop hl         ; HL: the last byte of the sorted run
 pop bc
 djnz .next
 ret

jr does not know the pe condition, hence the jp. And the dec l trick goes away: whichever way the loop ends, DE points at the freed place.

The guards

Now come the tests that pass as soon as they are written, the guards. Each one must prove that it can fail: we break the routine on purpose, and check that it turns red.

The first one repeats the one of selection sort: a smaller byte right after the array (insertion/12-guard):

Bytes Expected
#42, #30, #05, #17, #99 (B = 5), and #00 at #8005, right after the array #05, #17, #30, #42, #99 in memory, and nothing changed after #8004
The test in TypeScript 
it("ignores a smaller byte right after the array", () => {
  // Fresh memory already holds #00 there: this test says so out loud.
  const run = program.run("insertion_sort", {
    registers: { hl: ARRAY, b: 5 },
    memory: [{ at: ARRAY, bytes: [0x42, 0x30, 0x05, 0x17, 0x99, 0x00] }],
  });

  expect(run).toChangeOnly({ address: ARRAY, length: 5 });
  expect(run.memory(ARRAY, 5)).toEqual([0x05, 0x17, 0x30, 0x42, 0x99]);
});

Without the dec b at entry, the sort makes one pass too many, and inserts the byte that follows the array. The older tests fail too, but only thanks to the #00 of fresh memory. With #FF after the array, the broken version would pass them all. The guard says so out loud:

Error: Memory changed outside #8000-#8004:
  #8005  #00 -> #99

The best case

The next three guards set the budgets, for 2, 16 and 255 bytes. First the best case, sorted bytes (insertion/13-guard):

Bytes Expected
n rising bytes, #00, #01, #02…, for n = 2, 16 and 255 33n − 26 NOPs at most: 40, 502 and 8 389
The test in TypeScript 
// Sorted bytes are the fastest input: each key stops at the byte before it.
it.each([2, 16, 255])("sorts %i sorted bytes in 33n − 26 NOPs at most", (n) => {
  const sorted = Array.from({ length: n }, (_, i) => i);

  expect(insertionSort(sorted).nops).toBeLessThanOrEqual(33 * n - 26);
});

The count can be done by hand. A pass where the key does not move costs 33 NOPs: inc c 1, push bc 4, ld d,h 1, ld e,l 1, inc e 1, push de 4, ld a,(de) 2, ld b,0 2, cp (hl) 2, jr nc 3, ld (de),a 2, pop hl 3, pop bc 3, djnz 4.

Part NOPs
Entry: dec b 1, ret z that does not return 2, ld c,0 2 5
Each of the n − 1 passes 33
End: the last djnz costs 1 NOP less, then ret −1 + 3

The sum gives 33n − 26 NOPs. This guard catches the sentinel, which pays for its first pass:

AssertionError: expected 47 to be less than or equal to 40
AssertionError: expected 566 to be less than or equal to 502
AssertionError: expected 9409 to be less than or equal to 8389

Equal bytes

Then equal bytes, the worst case of selection sort (insertion/14-guard). Here, they are also the best case: cp (hl) sets the carry only if the key is strictly smaller, so a key never moves past an equal byte. The guard reuses the budget of sorted bytes:

Bytes Expected
n bytes equal to #42, for n = 2, 16 and 255 33n − 26 NOPs at most: 40, 502 and 8 389
The test in TypeScript 
// A key never moves past a byte equal to it.
it.each([2, 16, 255])("sorts %i equal bytes in 33n − 26 NOPs at most", (n) => {
  const equal = Array.from({ length: n }, () => 0x42);

  expect(insertionSort(equal).nops).toBeLessThanOrEqual(33 * n - 26);
});

The broken version it aims at compares with ≤ instead of <: a jr z before the jr nc moves the key past equal bytes. Equal bytes then become almost as slow as reversed bytes:

AssertionError: expected 48 to be less than or equal to 40
AssertionError: expected 1987 to be less than or equal to 502
AssertionError: expected 428124 to be less than or equal to 8389

This guard is not the only one to catch it. The jr z costs 2 NOPs on every comparison, even when it does not jump, and the guard on sorted bytes fails too: 42 NOPs instead of 40 for two bytes. But that one barely sees it, while the guard on equal bytes shows the full extent of the damage.

The worst case

What is left is the worst case, reversed bytes (insertion/15-guard):

Bytes Expected
n falling bytes, from n − 1 down to #00, for n = 2, 16 and 255 6n² + 22n − 21 NOPs at most: 47, 1 867 and 395 739
The test in TypeScript 
// Reversed bytes are the slowest input: each key moves past the whole sorted run.
it.each([2, 16, 255])("sorts %i reversed bytes in 6n² + 22n − 21 NOPs at most", (n) => {
  const reversed = Array.from({ length: n }, (_, i) => n - 1 - i);

  expect(insertionSort(reversed).nops).toBeLessThanOrEqual(6 * n * n + 22 * n - 21);
});

On the k-th pass, the key moves past the k bytes of the sorted run. Outside the inner loop, the pass costs 28 NOPs: the 33 of the best case, minus the cp (hl) and the jr nc that left the loop. Each shifted byte adds 12 NOPs.

Part NOPs
Entry 5
Pass k, for k = 1 to n − 1 28 + 12k
End: the last djnz costs 1 NOP less, then ret −1 + 3

The sum gives 6n² + 22n − 21 NOPs. This guard catches the exchanges:

AssertionError: expected 2272 to be less than or equal to 1867
AssertionError: expected 554362 to be less than or equal to 395739

It also catches the E counter:

AssertionError: expected 2092 to be less than or equal to 1867
AssertionError: expected 490608 to be less than or equal to 395739

For two bytes, both versions stay under the ceiling: the gap grows with n. The sentinel, already caught by the guard on sorted bytes, fails here too: 1 991 NOPs instead of 1 867 for 16 bytes.

Selection against insertion

Both sorts now have their formulas, on the same three inputs:

Input selection insertion
sorted bytes 5n² + 36n − 36 33n − 26
equal bytes 6n² + 35n − 36 33n − 26
reversed bytes ⌊11n²/2⌋ + 36n − 36 6n² + 22n − 21

And for 255 bytes:

Input selection insertion
sorted bytes 334 269 8 389
equal bytes 399 039 8 389
reversed bytes 366 781 395 739

On a sorted array or on equal bytes, insertion sort is linear, and 40 to 48 times faster than selection sort. On a reversed array, it is the other way round, past a certain size. Up to 26 bytes, insertion stays ahead (4 607 NOPs against 4 618), but from 27 bytes, selection wins (4 945 against 4 947). Insertion moves each byte one step at a time, at 12 NOPs a step, whereas selection searches for a long time but writes only one exchange per pass.

What is left is to compare the worst cases: 399 039 NOPs for selection, on equal bytes, and 395 739 for insertion, on reversed bytes. They are less than one percent apart, which we can call a draw, with about 20 frames of 19 968 NOPs on each side to sort 255 bytes.

Conclusion

The measurements of z80-tdd chose the LDD version, and three guards keep that choice: a change that slows down one of the three measured cases makes a test fail. On a sorted array, insertion sort is 40 times faster than selection sort, and in the worst case, the two sorts tie.

The routine has its restrictions:

The next post moves on to bubble sort.

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 insertion branch of the z80-tdd-sorts repository. It starts from main, not from selection, since insertion sort does not need find_min. To replay a step:

git checkout insertion/01-red
pnpm install
pnpm test

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