title: Translate Quicksort from C into MIPS assembly?
body: <p>I am trying to create a MIPS program of the Quicksort algorithm that sorts strings.
  I have a bit of C code that I am trying to translate, but I'm having an extremely hard time with it.</p>
  
  <p>Here's the C code:</p>
  
  <pre><code>// QuickSortIdx (using array indexing)
  //      array is a pointer to the first element of an array of string pointers
  //      left is the lowest index to begin sorting at (initially 0)
  //      right is the highest index to end sorting at (initially array length - 1)
  
  void quickSortIdx(char** array, int left, int right) {
      int i = left;
      int j = right;
  
      int pivotIndex = (i + j) &gt;&gt; 1;      // Arbitrarily pick middle element
      char* pivot = array[pivotIndex];    // as the pivot element
  
      // this loop is the partitioning step which divides the array into
      // two areas, elements greater than the pivot and elements less than the pivot
      do {
          // move i down to first element greater than or equal to pivot
          while (strcmp(array[i],pivot) &lt; 0) i++;
          // move j up to first element less than or equal to pivot
          while (strcmp(array[j],pivot) &gt; 0) j--;
  
          if (i &lt;= j) {                   // if i and j have not passed each other
              char* temp = array[i];
              array[i] = array[j];        // swap their respective elements
              array[j] = temp;
              i++;  j--;                  // advance both i and j
          }
      } while (i &lt;= j);   // Continue until i passes j
  
      // now sort the two partitions separately
      if (left &lt; j)  quickSortIdx(array,left,j);
      if (i &lt; right) quickSortIdx(array,i,right);
  }
  </code></pre>
  
  <p>and here is the MIPS code that I have so far:</p>
  
  <pre><code>.data
  str0:       
      .asciiz "Four"
  str1:       
      .asciiz "score"
  str2:       
      .asciiz "and"
  sarray:     
      .word   str0
      .word   str1                
      .word   str2
  size:   
      .word 3
  newline
      .asciiz "/n"
  
  main:
      la $s0, sarray              # s0 = array
      jal quickSort
  
  quickSort:
      li $t0, size                # t0 = size
      li $s2, $zero               # s2 = left
      subi $s3, $t0, 1            # t1 = right = size - 1
      addi $s4, $s2, $s3          # s3 = pivotIndex = left + right    
      sra $s4, $s4, 1             # s3 = pivotIndex = (left + right) / 2  
      ble $s2, $s3, innerSort         # if left &gt;= right, go to innerSort
  
  innerSort:
      lw $s5, $s2($s0)            # s5 = str1 = array[i]
      lw $s6, $s3($s0)            # s6 = str2 = array[j]
      lw $s7, $s4($s0)            # s7 = pivot = array[pivotIndex]
      jal strcmp_loop_1           # s1 = strcmp(array[i], pivot)
      bltz $s1, incrementI            # if s1 &lt; 0
      jal strcmp_loop_2           # s1 = strcmp(array[j], pivot)
      bgtz $s1, decrementJ            # if s1 &gt; 0
      ble $s2, $s3, swap          # if i &lt;= j
  
  swap:
      lw $t0, $s2($s0)            # t0 = temp = array[i]
      lw $t1, $s3($s0)            # t1 = temp = array[j]
      lw $s2($s0), $t1            # array[i] = array[j]
      lw $s3($s0), $t0            # array[j] = array[i]
      addi $s2, $s2, 1            # i++
      subi $s3, $s3, 1            # j--
      ble $s2, $s3, innerSort
      jal partition
  
  incrementI:
      addi $s2, $s2, 1            # i++
  
  decrementJ:
      subi $s3, $s3, 1            # j--
  
  strcmp_loop_1:
      lb $t0, 0($s5)              # t0 = 1st char of array[i] = str1
      lb $t1, 0($s7)              # t1 = 1st char of pivot = str2
      lw $t2, newline             # t2 = newline
      bne $t0, $t1, strcmp_notEqual_1     # end if chars are different
      beq $t0, $t2, strcmp_checkEnd_1     # if end of str1 is a newline, check end of str2
      addi $s5, $s5, 1            # increment str1 address
      addi $s7, $s7, 1            # increment str2 address
      jal strcmp_loop_1           # go to strcmp loop
  
  strcmp_checkEnd_1:
      lw $t2, newline             # t2 = newline
      beq $s7, $t2, strcmp_equal      # check if end of str2 is newline
      jal strcmp_notEqual_1           # if not, they aren't equal
  
  strcmp_equal:
      li $s1, $zero               # if equal, print out a 0 and end
      jal innerSort               
  
  strcmp_notEqual_1:
      sub $s1, $s5, $s7           # if not equal, subtract str2 from str1 and print
      beq $a0, -59, strcmp_equal      
      jal innerSort               
  
  strcmp_loop_2:
      lb $t0, 0($s6)              # t0 = load 1st character of str1 into $s0
      lb $t1, 0($s7)              # t1 = load 1st character of str2 into $s1
      lw $t2, newline             # t2 = newline
      bne $t0, $t1, strcmp_notEqual_2     # end if chars are different
      beq $t0, $t2, strcmp_checkEnd_2     # if end of str1 is a newline, check end of str2
      addi $s6, $s6, 1            # increment str1 address
      addi $s7, $s7, 1            # increment str2 address
      jal strcmp_loop_2           # go to strcmp loop
  
  strcmp_notEqual_2:
      sub $s1, $s6, $s7           # if not equal, subtract str2 from str1 and print
      beq $a0, -59, strcmp_equal      
      jal innerSort       
  
  strcmp_checkEnd_2:
      lw $t2, newline             # t2 = newline
      beq $s7, $t2, strcmp_equal      # check if end of str2 is newline
      jal strcmp_notEqual_2           # if not, they aren't equal
  
  partition:
  </code></pre>
  
  <p>I don't really know if any of my MIPS code is correct or if it works, and I'm especially stuck on the partitioning part (last two lines of recursive code in the C) and I have no idea how to go about it.</p>
  
  <p>Would anyone be willing to help me figure out how to do this?
  Thank you so much.</p>