.data
v: .word   3, 10, 8, 2, 7, 1, 5, 9, 6, 4


# swap(int i, int j) : swaps elements of v[] 
#   at positions i and j 
# $a0 = i
# $a1 = j
# $s0 = v
.text
swap:
	# intro - stack-frame
	addi    $sp, $sp, -28
	sw      $ra, 24($sp)
	sw      $fp, 20($sp)

	sw      $s0, 16($sp)    # v
	sw      $t0, 12($sp)    # temp
	sw      $t1, 8($sp)     # *v[i]
	sw      $t2, 4($sp)     # *v[j]
	sw      $t3, 0($sp)     # buffer
	addi    $fp, $sp, 24


	move    $t1, $s0        # pointer assignements
	sll     $a0, $a0, 2
	add     $t1, $t1, $a0
	move    $t2, $s0
	sll     $a1, $a1, 2
	add     $t2, $t2, $a1

	lw      $t0, 0($t1)     # temp = v[i]
	lw      $t3, 0($t2)     # v[i] = v[j]
	sw      $t3, 0($t1)
	sw      $t0, 0($t2)     # v[j] = temp

	# epilogue - stack-frame
	lw      $t3, 0($sp)
	lw      $t2, 4($sp)
	lw      $t1, 8($sp)
	lw      $t0, 12($sp)
	lw      $s0, 16($sp)

	lw      $fp, 20($sp)
	lw      $ra, 24($sp)
	addi    $sp, $sp, 28
	jr      $ra

# partition(int f, int l) : partitions elements in vector v[] 
#   between positions f and l, using as pivot the element v[l], such 
#   that 
#     i < p ==> v[i] <= v[p]
#     i > p ==> v[p] <  v[i]
#   The function returns the position p of the pivot.
# $a0 = f
# $a1 = l
# $s0 = v
# $v0 = p
.text
partition:
    # intro - stack-frame
    addi    $sp, $sp, -40
    sw      $ra, 36($sp)
    sw      $fp, 32($sp)

    sw      $s0, 28($sp)    # v
    sw      $s1, 24($sp)    # pivot
	sw		$s2, 20($sp)	# i
	sw		$s3, 16($sp)	# j
	sw		$s4, 12($sp)	# a0 (f)
	sw		$s5, 8($sp)		# a1 (l)
	sw		$t0, 4($sp)
	sw		$t1, 0($sp)
    addi    $fp, $sp, 36

	move	$s4, $a0
	move	$s5, $a1
	move    $t0, $s0    # make *v[l]
	move	$t1, $a1	#  t1 = l
    sll     $t1, $t1, 2	#  t1 *= 4
    add     $t0, $t0, $t1
	lw		$s1, 0($t0)	# pivot = v[l]
	
	move	$s2, $s4	# i = f;

	# for () {
	move	$s3, $s4	# j = f;
   	_part_loop0:
	slt		$t0, $s3, $s5		 # j < l
   	beq		$t0, $0, _part_loop_end
		move	$t0, $s0	# make *v[j]
		move	$t1, $s3
		sll		$t1, $t1, 2
		add		$t0, $t0, $t1
		lw		$t1, 0($t0)	# t1 = v[j]
		# if (v[j] < pivot)
		slt		$t0, $t1, $s1
		beq		$t0, $0, _part_loop_else
		
		move 	$a0, $s2	# swap (i, j);
		move 	$a1, $s3
		jal  	swap
		addi	$s2, 1		# i++
		
   	_part_loop_else:
		addi	$s3, 1		# j++
		j		_part_loop0	# }
   _part_loop_end:
	move	$a0, $s2		# swap (i, l)
	move	$a1, $s5
	jal		swap
	
	move	$v0, $s2		#return i

	# epilogue - stack-frame
	lw      $t1, 0($sp)
	lw      $t0, 4($sp)
	lw      $s5, 8($sp)
	lw      $s4, 12($sp)
	lw      $s3, 16($sp)
	lw      $s2, 20($sp)
	lw      $s1, 24($sp)
	lw      $s0, 28($sp)

	lw      $fp, 32($sp)
	lw      $ra, 36($sp)
	addi    $sp, $sp, 40
	jr		$ra


# qsort(int f, int l) : sorts the elements of v[]
#    between positions f:l
# $a0 = f
# $a1 = l
# $s0 = v
.text
qsort:                          # qsort entry point
    # intro - stack-frame with 4byte local var @ fp
    addi    $sp, $sp, -28	# qsort
    sw      $ra, 24($sp)
    sw      $fp, 20($sp)

    sw      $s0, 16($sp)	# v
	sw		$s2, 12($sp)	# a0 (f)
	sw		$s3, 8($sp)		# a1 (l)
	sw		$t0, 4($sp)
    addi    $fp, $sp, 24

    move	$s2, $a0		# get f, l
    move	$s3, $a1
    # if (f < l) {
	slt		$t0, $s2, $s3
	beq		$t0, $0, _qsort_end

		move 	$a0, $s2	# pivot = partition(f, l);
		move 	$a1, $s3
		jal  	partition
		sw		$v0, 0($sp)

		move	$a0, $s2	# qsort(f, pivot - 1);
		lw		$t0, 0($sp)
		addi	$t0, $t0, -1
		move	$a1, $t0
		jal		qsort

		lw		$t0, 0($sp)	# qsort(pivot + 1, l);
		addi	$t0, $t0, 1
		move	$a0, $t0
		move	$a1, $s3
		jal		qsort
	# }
   	_qsort_end:
    # epilogue - stack-frame
	lw      $t0, 4($sp)
	lw      $s3, 8($sp)
	lw      $s2, 12($sp)
	lw      $s0, 16($sp)

	lw      $fp, 20($sp)
	lw      $ra, 24($sp)
	addi    $sp, $sp, 28
	jr      $ra             # return to caller


.text
.globl main
main:
        # intro - stack-frame
        addi    $sp, $sp, -12	# main
        sw      $ra, 8($sp)
        sw      $fp, 4($sp)
        sw      $s0, 0($sp)
        addi    $fp, $sp, 8

        li      $t0, 10

        li      $a0, 0
        li      $a1, 9
        la      $s0, v
        jal     qsort

        # epilogue - stack-frame
        lw      $s0, 0($sp)
        lw      $fp, 4($sp)
        lw      $ra, 8($sp)
        addi    $sp, $sp, 12
        jr      $ra