Question

Write a MIPS program that uses an implementation of quick sort to sort an array of numbers (Translate the following code into (Mars Assembly language).

Quicksort Implementation - C

int partition(int arr [] , int left , int right) {

int i=left, j=right;

int tmp;
int pivot = arr[(left + right) / 2];

while (i <= j) {
while (arr [ i ] < pivot)

i ++;
while (arr [ j ] > pivot)

j −−;

if (i <= j) {
tmp = arr[i];

arr[i] = arr[j]; arr[j] = tmp;
i ++;
j −−;

}

}

return i ;

}

void quickSort(int arr [] , int left , int right) {

int index = partition(arr, left , right);

if (left < index − 1)

quickSort(arr , left , index − 1);

if (index < right)
quickSort(arr , index , right );

}

Answer 1

Here is the solution of your problem:

Translate C language to MIPS Program

partition:

        daddiu  $sp,$sp,-48

        sd      $fp,40($sp)

        move    $fp,$sp

        sd      $4,16($fp)

        move    $3,$5

        move    $2,$6

        sll     $3,$3,0

        sw      $3,24($fp)

        sll     $2,$2,0

        sw      $2,28($fp)

        lw      $2,24($fp)

        sw      $2,0($fp)

        lw      $2,28($fp)

        sw      $2,4($fp)

        lw      $3,24($fp)

        lw      $2,28($fp)

        addu    $2,$3,$2

        srl     $3,$2,31

        addu    $2,$3,$2

        sra     $2,$2,1

        dsll    $2,$2,2

        ld      $3,16($fp)

        daddu   $2,$3,$2

        lw      $2,0($2)

        sw      $2,8($fp)

        b       .L2

        nop

.L4:

        lw      $2,0($fp)

        addiu   $2,$2,1

        sw      $2,0($fp)

.L3:

        lw      $2,0($fp)

        dsll    $2,$2,2

        ld      $3,16($fp)

        daddu   $2,$3,$2

        lw      $2,0($2)

        lw      $3,8($fp)

        slt     $2,$2,$3

        bne     $2,$0,.L4

        nop

        b       .L5

        nop

.L6:

        lw      $2,4($fp)

        addiu   $2,$2,-1

        sw      $2,4($fp)

.L5:

        lw      $2,4($fp)

        dsll    $2,$2,2

        ld      $3,16($fp)

        daddu   $2,$3,$2

        lw      $2,0($2)

        lw      $3,8($fp)

        slt     $2,$3,$2

        bne     $2,$0,.L6

        nop

        lw      $3,0($fp)

        lw      $2,4($fp)

        slt     $2,$2,$3

        bne     $2,$0,.L2

        nop

        lw      $2,0($fp)

        dsll    $2,$2,2

        ld      $3,16($fp)

        daddu   $2,$3,$2

        lw      $2,0($2)

        sw      $2,12($fp)

        lw      $2,0($fp)

        dsll    $2,$2,2

        ld      $3,16($fp)

        daddu   $2,$3,$2

        lw      $3,4($fp)

        dsll    $3,$3,2

        ld      $4,16($fp)

        daddu   $3,$4,$3

        lw      $3,0($3)

        sw      $3,0($2)

        lw      $2,4($fp)

        dsll    $2,$2,2

        ld      $3,16($fp)

        daddu   $2,$3,$2

        lw      $3,12($fp)

        sw      $3,0($2)

        lw      $2,0($fp)

        addiu   $2,$2,1

        sw      $2,0($fp)

        lw      $2,4($fp)

        addiu   $2,$2,-1

        sw      $2,4($fp)

.L2:

        lw      $3,0($fp)

        lw      $2,4($fp)

        slt     $2,$2,$3

        beq     $2,$0,.L3

        nop

        lw      $2,0($fp)

        move    $sp,$fp

        ld      $fp,40($sp)

        daddiu  $sp,$sp,48

        j       $31

        nop

quickSort:

        daddiu  $sp,$sp,-64

        sd      $31,56($sp)

        sd      $fp,48($sp)

        sd      $28,40($sp)

        move    $fp,$sp

        lui     $28,%hi(%neg(%gp_rel(quickSort)))

        daddu   $28,$28,$25

        daddiu  $28,$28,%lo(%neg(%gp_rel(quickSort)))

        sd      $4,16($fp)

        move    $3,$5

        move    $2,$6

        sll     $3,$3,0

        sw      $3,24($fp)

        sll     $2,$2,0

        sw      $2,28($fp)

        lw      $3,28($fp)

        lw      $2,24($fp)

        move    $6,$3

        move    $5,$2

        ld      $4,16($fp)

        ld      $2,%got_disp(partition)($28)

        move    $25,$2

        nop

        sw      $2,0($fp)

        lw      $2,0($fp)

        addiu   $2,$2,-1

        lw      $3,24($fp)

        slt     $2,$3,$2

        beq     $2,$0,.L10

        nop

        lw      $2,0($fp)

        addiu   $2,$2,-1

        move    $3,$2

        lw      $2,24($fp)

        move    $6,$3

        move    $5,$2

        ld      $4,16($fp)

        ld      $2,%got_disp(quickSort)($28)

        move    $25,$2

        nop

.L10:

        lw      $3,0($fp)

        lw      $2,28($fp)

        slt     $2,$3,$2

        beq     $2,$0,.L12

        nop

        lw      $3,28($fp)

        lw      $2,0($fp)

        move    $6,$3

        move    $5,$2

        ld      $4,16($fp)

        ld      $2,%got_disp(quickSort)($28)

        move    $25,$2

        nop

.L12:

        nop

        move    $sp,$fp

        ld      $31,56($sp)

        ld      $fp,48($sp)

        ld      $28,40($sp)

        daddiu  $sp,$sp,64

        j       $31

        nop

// happy coding :)