用 MIPS 汇编语言实现快速排序

一个用 MIPS 汇编语言实现的快速排序。这里使用的 MIPS 指令仅仅是真实 MIPS 机器指令集的一小一部分，同时又扩充了一些如 jalr（用来在 jr 之前把返回地址存入 $31）之类的方言式指令。程序默认 $1 保存了内存中一个数组的首地址，$2 是其长度。程序入口点是一段测试代码，调用快速排序将数组排序，并找到所有元素的中数，保存到 $3 中。

;; entry point

        sw      $31,    -4($30)
        lis     $31
        .word   4
        sub     $30,    $30,    $31

        lis     $4
        .word   0
        mult    $2,     $31
        mflo    $5
        sub     $5,     $5,     $31
        lis     $29
        .word   qsort
        jalr    $29                                     ; call qsort to sort the array

        lis     $31
        .word   4
        add     $30,    $30,    $31
        lw      $31,    -4($30)

;; find the element at the midpoint of the sorted array
        lis     $4
        .word   2
        div     $2,     $4
        mflo    $4
        lis     $5
        .word   4
        multu   $4,     $5
        mflo    $4
        add     $4,     $4,     $1

        lw      $3,     0($4)

        jr      $31

;;
;; qsort
;;
;; $1 <- address of array
;; $3 <- return value
;; $4 <- @param - left bound
;; $5 <- @param - right bound
;; $6 <- left pointer
;; $7 <- right pointer
;; $8 <- pivot
;; $28 <- temporary storage
;; $29 <- temporary storage

qsort:
;; store registers used
	sw	$4,	-4($30)
	sw	$5,	-8($30)
	sw	$6,	-12($30)
	sw	$7,	-16($30)
	sw	$8,	-20($30)
	sw	$28,	-24($30)
	sw	$29,	-28($30)

;; base case
	slt	$29,	$4,	$5
	beq	$29,	$0,	ret			; if left bound >= right bound then return

;; initialization
        add     $6,     $4,     $1
        add     $7,     $5,     $1
        lw      $8,     0($6)                           ; pivot = *lp


;; main loop - while left pointer = pivot

        lw      $29,    0($7)
        slt     $28,    $29,    $8
        bne     $28,    $0,     bilp1

        lis     $28
        .word   4
        sub     $7,     $7,     $28                     ; rp -= 1

        beq     $0,     $0,     olp
bilp1:
;; inner loop 1 - break

        sw      $29,    0($6)                           ; *lp = *rp
        lis     $28
        .word   4
        add     $6,     $6,     $28                     ; lp += 1

;; inner loop 2 - while *lp = rp) break outer loop

        lw      $29,    0($6)
        slt     $28,    $29,    $8
        beq     $28,    $0,     bilp2

        lis     $28
        .word   4
        add     $6,     $6,     $28                     ; lp += 1

        beq     $0,     $0,     ilp2
bilp2:
;; inner loop 2 - break

        sw      $29,    0($7)                           ; *rp = *lp
        lis     $28
        .word   4
        sub     $7,     $7,     $28                     ; rp -= 1

        beq     $0,     $0,     olp
bolp:
;; main loop - break

        sw      $8,     0($6)                           ; *lp = pivot

;; recurse left
        lw      $4,     -4($30)

        sw      $31,    -32($30)
        lis     $31
        .word   32
        sub     $30,    $30,    $31

        lis     $29
        .word   4
        sub     $5,     $6,     $29                     ; right bound = lp - $1 - 1
        sub     $5,     $5,     $1
        lis     $29
        .word   qsort
        jalr    $29

        lis     $31
        .word   32
        add     $30,    $30,    $31
        lw      $31,    -32($30)

; recurse right
        lw      $5,     -8($30)

        sw      $31,    -32($30)
        lis     $31
        .word   32
        sub     $30,    $30,    $31

        lis     $29
        .word   4
        add     $4,     $6,     $29                     ; left bound = lp -$1 + 1
        sub     $4,     $4,     $1
        lis     $29
        .word   qsort
        jalr    $29

        lis     $31
        .word   32
        add     $30,    $30,    $31
        lw      $31,    -32($30)

ret:
;; restore registers used
        lw      $29,    -28($30)
        lw      $28,    -24($30)
        lw      $8,     -20($30)
        lw      $7,     -16($30)
        lw      $6,     -12($30)
        lw      $5,     -8($30)
        lw      $4,     -4($30)

        jr      $31