Straight Selection Sort in Python with Knuth's MMIX code in the comments

straightselectionsort.py

def selection_sort_mmix(records):
    """
    Sorts a list of records in place using the selection sort algorithm
    as described in the MMIX assembly program.
    
    The algorithm finds the maximum element in the unsorted portion
    and exchanges it with the element at the current end position (j).
    """
    N = len(records)
    
    # The MMIX code assumes N >= 2. If not, the list is already sorted.
    if N < 2:
        return records

    # --- S1. Loop on j. j <- N. ---
    # In MMIX: 01 START ENT1 N-1  (Sets rI1 = N-1, which is j-1)
    # The outer loop decrements rI1 until it's no longer positive.
    # So, 'j' goes from N down to 2.
    j = N
    
    while j > 1: # Corresponds to MMIX line 15 J1P 2B (Jump to start of loop if rI1 > 0)
        
        # --- S2. Find max(K_1, ..., K_j). k <- j - 1. ---
        # MMIX: 02 2H ENT2 0,1 (Sets rI2 = rI1, which is k = j-1)
        k = j - 1 # Current search position
        
        # i <- j.
        # MMIX: 03 ENT3 1,1 (Sets rI3 = rI1+1, which is i = (j-1)+1 = j)
        i = j # Index of the current maximum
        
        # rA <- K_i.
        # MMIX: 04 LDA INPUT,3 (Loads record at index rI3 into rA)
        # Convert 1-based index i to 0-based index for Python.
        rA = records[i - 1] # Holds the current maximum value
        
        # Inner loop to find the actual maximum value and its index
        while k > 0: # Corresponds to MMIX line 10 J2P 8B (Jump back if k > 0)
            
            # MMIX: 05 8H CMPA INPUT,2 (Compare rA with record at index rI2, i.e., K_k)
            # MMIX: 06 JGE *+3 (Jump if rA >= K_k)
            
            # Condition for 'Otherwise' (if K_k > rA):
            if records[k - 1] > rA: 
                
                # Otherwise set i <- k.
                # MMIX: 07 ENT3 0,2 (rI3 = rI2, so i = k)
                i = k
                
                # rA <- K_i.
                # MMIX: 08 LDA INPUT,3 (rA = K_i, the new maximum)
                rA = records[i - 1]
                
            # k <- k - 1.
            # MMIX: 09 DEC2 1 (rI2 = rI2 - 1)
            k -= 1
            
        # --- S3. Exchange with R_j. ---
        # At this point, 'i' is the index of the maximum from R_1 to R_j,
        # and 'rA' holds its value. The MMIX code uses 'rA' and 'rX' to perform the exchange.
        
        # MMIX: 11 LDX INPUT+1,1 (Loads record at index rI1+1 into rX, which is R_j)
        # R_j is the element at the 0-based index [j-1]
        record_j = records[j - 1]
        
        # R_i <- R_j.
        # MMIX: 12 STX INPUT,3 (Stores rX into record at index rI3, which is R_i)
        records[i - 1] = record_j
        
        # R_j <- rA.
        # MMIX: 13 STA INPUT+1,1 (Stores rA into record at index rI1+1, which is R_j)
        records[j - 1] = rA

        print(f"Step:   {records}")
        
        # Decrement j for the outer loop
        # MMIX: 14 DEC1 1 (rI1 = rI1 - 1)
        j -= 1
        
    return records


# Example Usage
if __name__ == "__main__":
    unsorted_list = [8, 4, 3, 7, 5, 2, 9, 1, 6]
    print(f"Unsorted: {unsorted_list}")

    sorted_list = selection_sort_mmix(unsorted_list)
    print(f"Sorted:   {sorted_list}")