Diamond Sort in MIPS/C

Say we have a diamond (85 elements in a 13*13 array) Every element has two parameters, a/b We need to sort the diamond so that:

1. the [a] parameter increases in each column.
2. the [b] parameter increases in each row.

What we want to get is like this: (the * is the part that is not defined in memory)

(this is an easy one 13 elements in a 5*5 array)

original:

*    *   4/3   *   *
*   1/3  2/3  4/5  *
1/2 3/1  2/5  3/6 2/7
*   2/3  1/2  5/2  *
*    *   6/1   *   *

sorted:

*    *   1/3   *   *
*   1/2  2/3  2/5  *
1/2 2/3  4/5  3/6 2/7
*   3/1  5/2  4/3  *
*    *   6/1   *   *

My algorithm is to bubble sort (according to a) all the values, then sort in each line according to the b parameter. This works pretty good but the dynamic instructions would be over 80000 (which should be O[n^2]). The bubble sort sucks hard in MIPS 'cause you need >10 instr. for each check (in bubble).

I want to know if there is better algorithm that reduces the dynamic instructions under 14000. BTW only use <=15 register and <=66 static instructions (which is 66 lines of code).

findnum:    addi    $27, $27, 4
            lw  $21, 0($27)
            beq $21, $0, findnum    # find the next nonzero number


bsort:      lw  $20, 0($25)             # load first number            
            slt $12, $21, $20       # if second < first $12=1
            bne $12, $15,  back     # $15 is constant 1
            sw  $21, 0($25)
            sw  $20, 0($27)
back:       addi    $25, $27, 0     # now second number is first number
            bne $27, $26, findnum   # $27 not the end then continue         



loop:       addi    $25, $01, 24
            addi    $27, $25, 0     # reinitialize the number
            addi    $10, $10, 1     # i++
            bne     $10, $11, findnum   # if i not equal to 85 jump back    

This is the core part of my code. $25 and $27 are initialized as the address of the first value of the array. $26 is the address of the last value.

Thanks a lot!