Sorting

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 Speed of Merge Sort Merge Sort is another highly efficient sorting algorithm that runs in optimal $O(n \log n)$ time, regardless of the initial state of the data. It is highly valued for its predictability and stability (it preserves the relative order of equal elements). The Principle: Merge Sort is a recursive algorithm that continually splits the array into two halves until it has many arrays of size one. It then merges these small, sorted arrays back together in the correct order. ...

The Drawback of Insertion Sort Insertion Sort (Part 96) is very fast for nearly sorted data, but slow for completely unsorted data because it can only move an element one position at a time. An element near the end must be swapped many times to reach the beginning. The Solution: Shell Sort Shell Sort (invented by Donald Shell) is an enhancement of Insertion Sort. It allows for large moves by sorting elements that are far apart, drastically reducing the number of total comparisons needed. ...

The Advantage of Selection Sort Both Bubble Sort (Part 94) and Insertion Sort (Part 96) frequently swap adjacent elements, leading to many memory write operations. If you are sorting data that resides on a slow medium (like a disk cache) or requires complex I/O to access, minimizing these writes is critical. Selection Sort does exactly this. The Principle: Selection Sort makes one pass over the unsorted portion of the array to select the smallest (or largest) element. It then performs only one swap to move that selected element into its final sorted position. ...

The Advantage of Insertion Sort While Quicksort (Part 95) is fastest for large, random arrays, Insertion Sort is often faster for two specific scenarios: Small Arrays: Its low overhead makes it faster than Quicksort for arrays under 20-30 elements. Nearly Sorted Arrays: It is extremely fast, running in nearly linear time ($O(n)$), if the array is already mostly sorted. The Principle: The algorithm builds the final sorted array one item at a time. It iterates through the input elements and inserts each element into its correct position within the already sorted portion of the array. ...

The Need for Quicksort While Bubble Sort (Part 94) is easy, its slow $O(n^2)$ time complexity makes it unusable for sorting large arrays. Quicksort is the fastest widely used sorting algorithm, running in $O(n \log n)$ time on average, making it ideal for sorting large high-score tables or data structures. The Principle: Quicksort uses a “divide-and-conquer” strategy: it picks an element (the pivot) and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. It then recursively sorts the sub-arrays. ...

The Need for Sorting Sorting arrays of data (e.g., high scores, tile IDs, or inventory items) is a fundamental task. While complex algorithms exist, Bubble Sort is the simplest to implement on the Z80 due to its minimal memory requirements and straightforward logic. The Principle: Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until no swaps are needed, meaning the list is sorted. ...