Sorting Algorythms

This program implements three sorting algorithms — Bubble Sort, Insertion Sort, and Shell Sort — as machine code routines embedded directly in the BASIC listing’s REM statements. The machine code begins at address 26715, with the three sort entry points at 26721, 26759, and 26800 respectively. Each routine operates on a linear array of fixed-length elements stored in memory, treating the first byte of each element as the most significant byte. The variables Length (element width in bytes), Start (address of the first element), and Size (number of elements) are stored as 16-bit words at addresses 26715, 26717, and 26719. The routines are called via RANDOMIZE USR and are noted as non-relocatable, with a Zeus Assembler source file distributed separately on tape.

---

Program Structure

The program is almost entirely contained within REM statements. Lines 1 through 8 carry all the executable content — machine code in line 1, documentation in lines 2–8 — while line 10 is the only active BASIC line, executing CLS followed by LIST 3 to display the title screen REM on startup.

Line	Purpose
1	Machine code payload (249 bytes) stored in REM
2	REM noting the 249-byte count
3	REM title screen / credits block
4	REM documentation: base address and entry points, variable layout
6	REM documentation: number storage format (MSB-first bytes)
7	REM documentation: worked example of memory layout
8	REM documentation: usage instructions and relocation warning
10	Active BASIC: CLS : LIST 3

Machine Code in REM

Storing machine code in a REM statement is a standard technique for embedding Z80 routines in a BASIC program without using POKE loops or a separate binary. The REM body is part of the program file and loads at a fixed address, making the routine available immediately. The author explicitly warns that the code is not relocatable — the three entry points (Bubble Sort at 26721, Insertion at 26759, Shell Sort at 26800) are hardcoded, and the base variables at 26715–26720 must sit at exactly those addresses for the routines to function correctly.

Memory Layout of Variables and Data

Three 16-bit control words are stored at the very start of the REM block (offset 6 from the line start, i.e., address 26715 in RAM):

• Length (26715/26716) — byte width of each element (LSB/MSB)
• Start (26717/26718) — address of the first element in the array
• Size (26719/26720) — number of elements to sort

Elements are stored as contiguous fixed-length byte strings with the most significant byte first, allowing the comparison logic in the sort routines to work with a simple byte-by-byte lexicographic comparison from MSB to LSB — a natural fit for Z80’s sequential memory access.

Sorting Algorithms Provided

1. Bubble Sort (entry 26721) — O(n²) worst case; simplest implementation
2. Insertion Sort (entry 26759) — O(n²) worst case; efficient for nearly-sorted data
3. Shell Sort (entry 26800) — O(n log n) to O(n^1.5) depending on gap sequence; the most performant of the three for larger arrays

Usage Pattern

The caller is expected to poke the Length, Start, and Size values into addresses 26715–26720 before invoking the desired routine with RANDOMIZE USR 26721 (or 26759 / 26800). The routines sort in-place, modifying the data directly in memory at the address given by Start.

Notable Techniques and Observations

• The 249-byte machine code count is explicitly cross-checked in line 2, suggesting the author was careful about the REM block length and the resulting absolute addresses.
• The Zeus Assembler source being distributed on the same tape is a useful detail: Zeus was a popular Z80 assembler of the era, and providing source allows hobbyists to relocate or modify the routines despite the non-relocatable binary.
• Line 10 uses LIST 3 rather than PRINT statements to display the credits, elegantly reusing the REM text that is already present in the program without duplicating it as string data.
• The absence of any POKE or LOAD machinery means this is a self-contained file: the machine code travels with the BASIC listing and is ready to use as soon as the program is loaded and run.

Bugs and Anomalies

There are no apparent bugs in the BASIC portion. The relocation limitation is a design constraint rather than a defect — it simply means the program must be loaded at the address for which it was assembled, which is the normal expectation for a non-relocatable machine code module stored in a REM statement at a fixed line number.