QUICKSORT IN MIPS

Question

I have written a quicksort algorrithm in MIPS assembly according to C++ code. In C++, it works very well but in MIPS, it doesn't work. I debugged it, and problem is recursion. This is the algorithm:

QuickSort(Data[], l , r)
{
    // If the first index less or equal than the last index
    if l <= r:
    {
        // Create a Key/Pivot Element
        key = Data[r]

        // Create temp Variables to loop through array
        i = l;
        j = r;

        while i <= j:
        {
            while Data[i] < key AND i < r:
                i = i + 1
            while Data[j] > key AND j > 0:
                j = j - 1
            if i <= j:
            {
                swap Data[i], Data[j]
                i = i + 1 
                j = j + 1
            }
        }

        if l < j:
            QuickSort(Data, l, j);
        if r > i:
            QuickSort(Data, i, r);
    }
}

This is MIPS code. It works in some cases. ex: array = {6, 5, 4, 3, 2, 1}. MIPS code:

#-function QuickSort(arr, left,right)
    #parameter
    #          $a0: array
    #          $a1: left
    #          $a2: right

QuickSort:
    subu $sp, $sp, 16
    sw   $a0, 0($sp)
    sw   $a1, 4($sp)
    sw   $a2, 8($sp)
    sw   $ra, 12($sp)

    la   $s0, 0($a0)
    move $s1, $a1
    move $s2, $a2

    bgt  $s1, $s2, done

    sll  $t3, $s2, 2
    add  $t3, $s0,$t3
    lw   $t2, 0($t3)

    move $t0, $s1
    move $t1, $s2

    WhileOuter:
        While_i:
            sll $t3, $t0, 2
            add $t3, $s0, $t3
            lw  $t4, 0($t3)

            bge $t4, $t2, EndWhile_i
            bge $t0, $s2, EndWhile_i
            addi $t0, $t0, 1    
            j While_i
        EndWhile_i:

        While_j:
            sll $t3, $t1, 2
            add $t3, $s0, $t3
            lw $t4, 0($t3)

            ble $t4, $t2, EndWhile_j
            blez $t1, EndWhile_j
            addi $t1, $t1, -1
            j While_j
        EndWhile_j:

        bgt $t0, $t1, EndWhileOuter

        #swap arr[i], arr[j]
        sll $t4, $t0, 2
        sll $t5, $t1, 2

        add $s3, $s0, $t4
        add $s4, $s0, $t5

        lw $t4, 0($s3)
        lw $t5, 0($s4)

        sw $t4, 0($s4)
        sw $t5, 0($s3)

        addi $t0, $t0, 1
        addi $t1, $t1, -1
        j WhileOuter
    EndWhileOuter:

    bge $s1, $t1, call2
    lw $a1, 4($sp)
    move $a2, $t1
    move $a0, $s0
    jal QuickSort

    call2:
    ble $s2, $t0, done
    move $a1, $t0
    lw $a2, 8($sp)
    move $a0, $s0
    jal QuickSort
    done:
    addu $sp, $sp, 16
    lw $a0, 0($sp)
    lw $a1, 4($sp)
    lw $a2, 8($sp)
    lw $ra, 12($sp) 

    jr $ra

Can anyone find the error(s) in this code? Thanks for any help.

Answer 1

1. You are using the saved registers $s0, $s1, $s2, but without following the requirement to preserve the values in those registers for the caller.

Thus, the callers of QuickSort are not guaranteed their $s registers will be preserved.

You aren't showing the rest of the code, e.g. the main.

However, we know that QuickSort calls itself, and, after the first recursive call to itself, it relies on the $s0 & $s2 registers, which should be ok, but we know they aren't properly preserved by QuickSort.

2. You need to more closely analyze your register usage and requirements.  The following code runs after the first (recursive) call to QuickSort.  It rightfully expects $s0 and $s2 to be preserved, but also expects $t0 to be preserved — which is a temporary register meaning it is not preserved by a call, so this is an error.

        jal QuickSort       # this call wipes out $t0
     call2:
        ble $s2, $t0, done  # what's supposed to be in $t0 here?
        move $a1, $t0
        lw $a2, 8($sp)
        move $a0, $s0

3. You have no requirement for saved register $s1 and should have chosen a temporary register for that usage instead.  I would have just used the variable in its original $a1 register.

4. You're saving $a0 register to memory but not using that memory location's value.

5. It is either missing or you've changed the location of the outer while loop's exit condition.  It is no longer at the top of the loop.  It now reads like this:

  while true:
        {
            while Data[i] < key AND i < r:
                i = i + 1
            while Data[j] > key AND j > 0:
                j = j - 1
            if i > j break;

6. The Python code does

       if i <= j:
       {
           swap Data[i], Data[j]
           i = i + 1 
           j = j + 1
       }
   

whereas after the swap the assembly code does i++ yet j-- .

7. You're using $s3 and $s4 but for simple temporary usages — use $t registers for these purposes instead.