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 Algorithm: The Partition Step

The heart of Quicksort is the Partition Routine.

The Goal: Rearrange the elements such that:

  1. The chosen pivot is in its final sorted position.
  2. All elements to the left of the pivot are smaller than it.
  3. All elements to the right of the pivot are larger than it.

Z80 Implementation Focus: The routine uses two pointers (HL′ and DE′) that move inward from the ends of the array segment, swapping elements until they cross.

Z80 Quicksort Requirements

Quicksort is much more complex to implement than Bubble Sort and relies on advanced Z80 techniques:

1. Recursion and the Stack: Quicksort is inherently recursive. Since the Z80 has no dedicated memory for recursion, the routine must use the CPU Stack (Part 3) to save the bounds (start and end addresses) of the sub-arrays it needs to sort later.

    ; Inside the Partition routine, after defining the new sub-arrays:
    PUSH HL             ; Save the Start Address of the new sub-array
    PUSH DE             ; Save the End Address of the new sub-array
    JP   QUICKSORT_ROUTINE ; Call recursively

2. Block Swapping: The Partition routine relies heavily on fast swapping of elements (Part 94) and 16-bit comparison (Part 87).

3. Choosing the Pivot: The pivot is often the first, middle, or last element. A poorly chosen pivot can degrade performance back to $O(n^2)$.

Advantage and Final Output

Advantage: Despite the complex code overhead, for lists larger than about 50 elements, Quicksort’s superior $O(n \log n)$ performance makes it significantly faster than simpler algorithms on the Z80.

Final Output: The main routine starts the recursion, and when the original call returns, the entire 16-bit or 8-bit array is sorted in memory.