.data
    .align  0       # string data doesn't have to be aligned
space:  .asciiz " "
lf: .asciiz "\n"
before: .asciiz "Before: "
after:  .asciiz "After: "
prompt: .asciiz "Enter Number: "

    .align  2       # word data must be on word boundaries
array:  .word   -1,-2,-5,-6,-9,-0,-7,-8,-3,-4

SIZE    = 10            # number of array elements
PRINT_STRING = 4            # arg for syscall to tell it to write
PRINT_INT = 1

    .text           # this is program code
    .align  2       # instructions must be on word boundaries

    .globl  main        # main is a global label

#
# EXECUTION BEGINS HERE
#
main:
    addi    $sp,$sp,-4  # allocate space for the return address
    sw  $ra,0($sp)  # store the ra on the stack

    la  $a0,array   # set up to read in an array of SIZE ints
    li  $a1,SIZE    # and put them at label array
    jal readarray

    li  $v0,PRINT_STRING    # print a "Before:"
    la  $a0,before
    syscall

    la  $a0,array   # print out the original array
    li  $a1,SIZE
    jal parray

        la      $a0, array
        li      $a1, SIZE
        jal     sort

    li  $v0,PRINT_STRING        # print "After: "
    la  $a0,after
    syscall

    la  $a0,array   # print the array again (now sorted)
    li  $a1,SIZE
    jal parray

    lw  $ra,0($sp)  # restore the ra
    addi    $sp,$sp,-4  # deallocate stack space
    jr  $ra     # return from main and exit spim


parray:
    li  $t0,0       # i=0;
    move    $t1,$a0     # t1 is pointer to array
pa_loop:
    beq $t0,$a1,done    # done if i==n

    lw  $a0,0($t1)  # get a[i]
    li  $v0,PRINT_INT
    syscall         # print one int

    li  $v0,PRINT_STRING
    la  $a0,space
    syscall         # print a space

    addi    $t1,$t1,4   # update pointer
    addi    $t0,$t0,1   # and count
    j   pa_loop
done:
    li  $v0,PRINT_STRING
    la  $a0,lf
    syscall         # print a newline

    jr  $ra


readarray:
    li  $t0,0       # i=0;
    move    $t1,$a0     # t1 is pointer to array
ra_loop:
    beq $t0,$a1,ra_done # done if i==n

    li  $v0,PRINT_STRING
    la  $a0,prompt
    syscall         # print one int

    li  $v0,5
    syscall
    sw  $v0,0($t1)

    addi    $t1,$t1,4   # update pointer
    addi    $t0,$t0,1   # and count
    j   ra_loop
ra_done:
    li  $v0,PRINT_STRING
    la  $a0,lf
    syscall         # print a message

    jr  $ra

sort:
    addi    $sp,$sp,-20 # set up our stack frame
    sw  $ra, 16($sp)    # save return address
    sw  $s3, 12($sp)    # save s0 through s3
    sw  $s2, 8($sp)
    sw  $s1, 4($sp)
    sw  $s0, 0($sp)

    move    $s2,$a0     # s2 points to the array element
    move    $s3,$a1     # s3 is the length


    move    $s0,$zero   # s0 is the outer loop control variable
for1tst:
    slt $t0,$s0,$s3 # have we reached the end?
    beq $t0,$zero,exit1 # yes - leave


    addi    $s1,$s0,-1  # s1 is the inner loop control variable
for2tst:
    slti    $t0,$s1,0   # j >= 0?
    bne $t0,$zero,exit2 # no - leave the inner loop

    add $t1,$s1,$s1 # scale the loop control variable
    add $t1,$t1,$t1 # t1 = s1 * 4
    add $t2,$s2,$t1 # t2 now points to v[j]

    lw  $t3,0($t2)  # get v[j]
    lw  $t2,4($t2)  # get v[j+1]
    slt $t0,$t2,$t3 # v[j] < v[j+1]?
    beq $t0,$zero,exit2 # yes - leave the inner loop

    move    $a0,$s2     # we found a pair of entries to swap
    move    $a1,$s1
    jal swap

    addi    $s1,$s1,-1
    j   for2tst
exit2:

    addi    $s0,$s0,1
    j   for1tst
exit1:

    lw  $s0, 0($sp) # restore our saved registers
    lw  $s1, 4($sp)
    lw  $s2, 8($sp)
    lw  $s3, 12($sp)
    lw  $ra, 16($sp)    # and return address
    addi    $sp,$sp,20  # destroy the stack frame
    jr  $ra     # and return to the caller

swap:
        sll     $t1, $a1, 2
        add     $t1, $a0, $t1
        lw      $t0, 0($t1)
        lw      $t2, 4($t1)
        sw      $t2, 0($t1)
        sw      $t0, 4($t1)
        jr      $ra