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 Critical Challenge: Temporary Memory

Merge Sort’s major drawback, especially on a Z80 with only 64KB of RAM, is its memory requirement.

The Problem: The merge operation requires a temporary scratchpad buffer that is nearly the size of the array being sorted. Sorting a 20KB array requires reserving an additional 20KB of free RAM.

The Algorithm: The Merge Step

The heart of the algorithm is the Merge Routine, which takes two adjacent sorted sub-arrays and combines them into one larger sorted array in the scratchpad buffer.

The Merge Process (Simplified):

  1. Use two pointers (HL′ and DE′) to track the current element in each of the two sub-arrays.
  2. Use a third pointer (`IX′) to write the result into the scratchpad buffer.
  3. Compare the elements at HL′ and DE′. Write the smaller one to `(IX)′.
  4. Increment the pointer of the element that was just moved.
  5. Repeat until one sub-array is empty, then copy the rest of the other sub-array.

Z80 Implementation Focus

The routine requires heavy recursion (Part 95), relying on the stack to save the bounds of the sub-arrays. It also relies on the 16-bit comparison routine (Part 87) for the core merge logic.

Memory Management Routine:

MERGE_SORT_MAIN:
    ; 1. Check Memory: Before starting, call the kernel's memory allocation routine
    CALL ALLOCATE_SCRATCHPAD ; Allocate N/2 bytes of temp RAM (Part 55)
    JP   C, OUT_OF_MEMORY     ; Check Carry flag for allocation failure

    ; 2. Recursive Split Phase (Uses Stack)
    CALL SPLIT_AND_SORT

    ; 3. Free Memory: After the sort is complete, release the scratchpad
    CALL FREE_SCRATCHPAD      
    RET

Efficiency Trade-off: Merge Sort is highly predictable and doesn’t suffer from Quicksort’s worst-case scenario. However, on memory-constrained systems like the Z80, the need to reserve a massive temporary buffer often restricts its use to smaller datasets where the memory overhead is manageable.