title: MIPS implementation of selection sort outputting correct values
body: <p>I am attempting to implement selection sort in MIPS. My output occasionally correct, but there are several instances where it is incorrect. Usually it is correct up until some point and after that point the numbers print out unsorted. It also appears to have difficulty with multiple negative numbers. </p>
  
  <p>I believe the issue may be with the swap function but I am not sure. 
  Any help would be greatly appreciated.</p>
  
  <p>Note: I am not allowed to use pseudo-instructions, such as bge or move.</p>
  
  <p>Here is my code in the C implementation I'm emulating.</p>
  
  <pre><code>.data
      msg1:   .asciiz "The elements sorted in ascending order are:"
              .align 2
      space:  .asciiz " "
                  .align 2
      comma:  .asciiz ","
                  .align 2
      arr:        .space 80
  .text
      MAIN:   
  
      # Ask for user input and put value in $s1
      addi $v0, $zero, 5      # call service 5 for integer input
      syscall             # read integer
      add $s1, $zero, $v0         # Save $t0 = len
  
      # Load address for arr
      la $s0, arr             # Pointer to arr goes in $t1
  
      add $a0, $zero, $s0     # Save arr pointer to $a0
      add $a1, $zero, $s1     # Save len to $a1
  
      # Ask for user input to fill arr
      jal FILL
  
      # Sort the list using selection sort
      jal SORT
  
      # Print list
      jal PRINT
  
      # Call to end program
      addi $v0, $zero, 10         # system call for exit
      syscall
  
  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
  
  FILL: # deal with stack and save
      addi $t0, $zero, 0      # $t0 = counter = 0
  
  FILL_LOOP:
      slt $t1, $t0, $a1       # if(counter &lt; len) continue
      beq $t1, $zero, FILL_RETURN     # if(counter &gt;= len) branch out of loop 
  
      addi $v0, $zero 5       # call service 5 for integer input
      syscall             # read integer
  
      addi $t2, $zero, 0      # clear $t2 and set to 0
      add $t2, $zero, $v0         # $t2 holds input integer
  
      add $t3, $zero, $t0         # $t3 = i
      sll $t3, $t3, 2         # $t3 =  counter * 4
      add $t3, $t3, $a0       # addr of arr[counter]
      sw $t2, 0($t3)          # store values in arr
  
      addi $t0, $t0, 1        # counter = counter + 1
  
      j   FILL_LOOP
  
  FILL_RETURN:
      jr $ra              # Return
  
  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
  
  SORT:
      addi $sp, $sp, -28  # make space for variables
      sw $a0, 0($sp)      # store $a0 (arr)
      sw $a1, 4($sp)      # store $a1 (len)
      sw $ra, 8($sp)      # store return address
      sw $s0, 12($sp)     # store $s0 ( i )
      sw $s1, 16($sp)     # store $s1 ( j )
      sw $s2, 20($sp)     # store $s2 (tmp)
      sw $s3, 24($sp)     # store $s3 (minIndex)
  
      addi $s0, $zero, 0  # i = 0
      add $t0, $zero, $a1 # $t0 = len
      addi $t0, $t0, -1   # $t0 = len - 1
  
  FOR_1:
      slt $t1, $s0, $t0   # i &lt; $t0 = len - 1 continue
      beq $t1, $zero, SORT_RETURN # if !(i &lt; len - 1) branch out of loop
  
      add $s3, $zero, $s0     # minIndex = i
      addi $t1, $s0, 1    # $t1 = i + 1
      add $s1, $zero, $t1     # j = $t1 = i + 1
  
  FOR_2: 
      slt $t1, $s1, $a1   # j &lt; len continue
      beq $t1, $zero, IF_1    # if !(j &lt; len) branch out of loop 
  
  IF_2: # "FIND MIN"
  
      # get value at arr[ j ] store in $t3
      add $t2, $zero, $s1     # calculate index $t2 = j 
      sll $t2, $t2, 2     # offset = $t2 * 4
      add $t2, $t2, $a0   # add offset to base address
      lw $t3, 0($t2)      # load value at arr[ j ] into $t3
  
       # get value at arr[minIndex] store in$t5
      add $t4, $zero, $s3     # calculate index $t4 = minIndex
      sll $t4, $t4, 2     # offset = $t4 * 4
      add $t4, $t4, $a0   # add offset to base address
      lw $t5, 0($t4)      # load value at arr[minIndex] into $t5
  
      slt $t1, $t3, $t5   # if(arr[ j ] &lt; arr[minIndex]) continue
      beq $t1, $zero, LOOP_2  # if !(arr[ j ] &lt; arr[minIndex]) branch out of if stmt
      add $s3, $zero, $s1     # minIndex = j
  
  LOOP_2:
      addi $s1, $s1, 1    # j++
      j FOR_2
  
  IF_1: # "SWAP"
      beq $s3, $s0, LOOP_1    # if(minIndex == i) branch out of if stmt (jump to LOOP_1)
  
  
      # tmp = arr[minIndex]
      add $t2, $zero, $s3     # calculate index $t2 = minIndex
      sll $t2, $t2, 2     # offset = $t2 * 4
      add $t2, $t2, $a0   # add offset to base address
      lw $s2, 0($t2)      # $s2 = tmp = arr[minIndex]
  
      # arr[minIndex] = arr[ i ]
      add $t3, $zero, $s0     # calculate index $t3 = i
      sll $t3, $t3, 2     # offset = $t2 * 4
      add $t3, $t3, $a0   # add offset to base address
      lw $t0, 0($t3)      # $t0 = arr [ i ]
  
      sw $t0, 0($t2)      # store value at arr[ i ] in arr[minIndex] 
  
      # arr[ i ] = tmp
      sw $s2, 0($t3)      # store tmp value in arr[ i ]           
  
  LOOP_1:
      addi $s0, $s0, 1    # i++
      j FOR_1 
  
  SORT_RETURN:
      lw $a0, 0($sp)      # Get $a0
      lw $a1, 4($sp)      # Get $a1
      lw $ra, 8($sp)      # Get return address
      lw $s0, 12($sp)     # Get $s0
      lw $s1, 16($sp)     # Get $s1
      lw $s2,  20($sp)    # Get $s2
      lw $s3, 24($sp)     # Get $s3
      addi $sp, $sp 28    # Adjust stack pointer
      jr $ra          # Return
  
  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
  
  PRINT:
      addi $t0, $zero, 0  # $t0 = counter = 0
      add $t1, $zero, $a0 # $t1 = arr address pointer
  
      # Print msg1
      la $s3, msg1
      add $a0, $zero, $s3     # put address of space in $a0 to print
      addi $v0, $zero, 4  # call service 4 to print a string
      syscall         # print string
  
      # Print a space
      la $s3, space
      add $a0, $zero, $s3     # put address of space in $a0 to print
      addi $v0, $zero, 4  # call service 4 to print a string
      syscall         # print string
  
  PRINT_LOOP:
      slt $t2, $t0, $a1   # if(counter &lt; len) continue
      beq $t2, $zero, PRINT_RETURN # if(counter &gt;= len) branch out of loop 
  
      add $t3, $zero, $t0     # $t3 = counter
      sll $t3, $t3, 2     # $t3 = counter * 4
      add $t3, $t3, $t1   # $t3 =  addr of arr[counter]
  
      lw $t4, 0($t3)      # Load value to print
      add $a0, $zero, $t4     # put address of $t4 in $a0 to print
  
      addi $v0, $zero, 1  # call service 1 to print integer
      syscall         # print integer
  
      # Check if last array element
      # Skip printing comma and space
      addi $t3, $a1, -1   # $t3 = len - 1
      beq $t3, $t0, PRINT_RETURN # if(at least element)
  
      # Print a comma
      la $s3, comma
      add $a0, $zero, $s3     # put address of space in $a0 to print
      addi $v0, $zero, 4  # call service 4 to print a string
      syscall         # print string
  
      # Print a space
      la $s3, space
      add $a0, $zero, $s3     # put address of space in $a0 to print
      addi $v0, $zero, 4  # call service 4 to print a string
      syscall         # print string
  
      addi $t0, $t0, 1    # counter - counter + 1
  
      j PRINT_LOOP
  
  PRINT_RETURN:
      jr $ra          # Return
  </code></pre>
  
  <p>C imp</p>
  
  <pre><code>  for ( c = 0 ; c &lt; ( n - 1 ) ; c++ )
    {
       position = c;
  
    for ( d = c + 1 ; d &lt; n ; d++ )
    {
       if ( array[position] &gt; array[d] )
          position = d;
    }
    if ( position != c )
    {
       swap = array[c];
       array[c] = array[position];
       array[position] = swap;
    }
   }
  </code></pre>