The Advantage of Insertion Sort

While Quicksort (Part 95) is fastest for large, random arrays, Insertion Sort is often faster for two specific scenarios:

  1. Small Arrays: Its low overhead makes it faster than Quicksort for arrays under 20-30 elements.
  2. 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 Insertion Sort Algorithm

The core of the algorithm involves shifting larger elements to the right to make a “hole” for the new element being inserted.

The Steps (Simplified):

  1. Iterate: Start with the second element ($A_1$) and iterate to the end.
  2. Store Key: Store the current element ($A_i$) in a temporary register (the key).
  3. Shift: Compare the key with the elements immediately to its left ($A_{i-1}, A_{i-2}, \dots$). If a left element is larger than the key, shift it one position to the right.
  4. Insert: Once a smaller or boundary element is found, insert the key into the resulting hole.

Z80 Implementation Focus

The shift-and-insert process relies on moving blocks of memory backward, making the `LDDR′ (Load, Decrement, Repeat) instruction (the reverse of LDIR) highly valuable.

The Shift Routine Logic:

SHIFT_AND_INSERT:
    ; Assume HL = Address of the element to the left of the insertion point (A_i-1)
    ; Assume DE = Address where the element will be inserted (A_i)
    ; Assume BC = Length of the block to shift (initially 1)

SHIFT_LOOP:
    ; 1. Check comparison (Compare Key with A_i-1)
    CALL COMPARE_KEY_TO_HL ; Sets flags based on Key vs (HL)
    JP   C, INSERT_HOLE    ; If Key < (HL), must shift and continue search.

    ; --- SHIFT REQUIRED ---
    PUSH HL, DE, BC         ; Save context
    CALL MEMCPY_SHIFT_BLOCK ; Use LDDR to shift A_i-1 to A_i
    POP  BC, DE, HL

    DEC  HL                 ; Move comparison pointer back
    INC  BC                 ; Adjust shift block size
    JP   SHIFT_LOOP         ; Continue shifting
    
INSERT_HOLE:
    ; HL points to the final hole position
    LD   A, KEY_VALUE
    LD   (HL), A            ; Insert the key into the hole
    RET

Efficiency Trade-off: Although Insertion Sort is $O(n^2)$ in the worst case (reverse-sorted array), its ability to handle the shifting and comparisons locally makes the constant factor very low on the Z80.