Advanced

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. ...

The Need for Fast Lookup If you have a large list of data (e.g., all font character pointers, or a list of game variables) that is sorted alphabetically or numerically, checking every item sequentially (`memchr′ in Part 89) is inefficient. Binary Search is the solution: it finds the target by repeatedly dividing the search space in half. The Principle: After each comparison, the algorithm eliminates half of the remaining elements. This makes the search time logarithmic, drastically speeding up large lookups. ...

The Need for a Detailed Compare The standard `memcmp′ routine (Part 89) tells you only if two blocks are the same or different. For debugging purposes, you often need to know where the corruption or difference first occurred. Goal: Compare two memory blocks, and if they differ, return the address of the first byte that does not match. The Comparison Strategy We will modify the simple comparison loop to preserve the address and exit immediately upon the first failure. ...

The Challenge of Integer Division The Z80 CPU has no instruction for division. Every division operation must be performed using software algorithms based on repeated subtraction or shifting and subtraction (the same method used for manual long division). Goal: Divide a 16-bit number (the Dividend) by an 8-bit number (the Divisor) to produce a 16-bit Quotient and an 8-bit Remainder. The Algorithm: Binary Long Division The most efficient method is to implement the Binary Long Division algorithm, which uses shifts and conditional subtraction. ...

The Need for Block Search and Compare In system programming, you need routines to: Search (memchr): Find the first occurrence of a specific character (e.g., a null terminator, space, or command byte) within a buffer. Compare (memcmp): Verify that two large blocks of memory (e.g., two versions of a game level, or a password against a stored hash) are identical. Routine 1: Block Search (memchr) Block Search scans a memory area for the first occurrence of a specific 8-bit value. ...