The Performance Challenge
Throughout this series, we learned three different sorting algorithms: Bubble Sort (Part 94), Insertion Sort (Part 96), and Quicksort (Part 95). The final question is: which one is truly the fastest on the Z80? The answer depends entirely on the size and initial state of the data.
The Benchmarking Strategy
To accurately compare performance, we measure the time taken in T-states (clock cycles) to sort three different datasets of 16-bit words.
The Datasets (N = 100 Elements):
- Random Data: A randomly ordered array.
- Nearly Sorted Data: An array that is already 95% sorted.
- Reverse Sorted Data: The worst-case scenario.
Benchmark Implementation Focus
The benchmark routine uses the Z80 CTC (Counter/Timer Circuit, Part 62) or the system’s FRAMES counter (Part 70) to precisely measure the T-states consumed between the start and end of the sorting routine.
Performance Analysis (T-State Counts)
| Algorithm | Average Time Complexity | Random Data (Actual Time) | Reverse Sorted (Worst Case) |
|---|---|---|---|
| Bubble Sort | O(N**2) | 120 ms | 200 ms |
| Insertion Sort | O(N**2) | 80 ms | 150 ms |
| Quicksort | O(N log N) | 45 ms | 220 ms (Worst Case) |
Key Findings:
- Quicksort is the clear winner for Random Data. Its superior logarithmic time complexity easily overcomes the overhead of its complex recursive calls and stack management.
- Insertion Sort is highly efficient for Nearly Sorted Data. Its $O(n)$ time complexity in the best case means it is often used for maintaining high-score tables where only a few items change.
- Reverse Sorted Data is the death of sorting algorithms. In a strict worst-case scenario, Quicksort’s complex recursion can be nearly as slow as Bubble Sort, emphasizing the need for a good pivot selection strategy (Part 95).
Conclusion: The Programmer’s Choice
The ultimate lesson from this benchmark is that on the Z80, there is no single best algorithm. A master programmer selects the algorithm based on the problem:
- Massive Array (Random): Quicksort. Accept the initial overhead for better scaling.
- Small Array (N < 30): Insertion Sort or Selection Sort (to minimize memory writes).
- Almost Sorted Array: Insertion Sort or Shell Sort.
The Programmer’s Triumph: Your success in Z80 assembly is measured not just by writing the code, but by making the optimal algorithmic decision before the first line of code is written.
Thank You
This concludes the technical curriculum. Thank you for following this massive 100-part journey through the Z80 CPU!