| HN Mirror

Here's a quicksort in 20 lines of ARM assembly, sorting an array of integers in memory starting at [r0] and ending at [r1] (i.e., inclusive bounds):

    quirks: push {r4, r5, r6, lr}
        4:  subs r2, r0, r1
            bhs 3f                  @ Exit if carry set (no borrow).
            mov r5, r1              @ This frees up r1 as a temp.

            mov r6, r0
            ldr r3, [r5]

        1:  ldr r4, [r5, r2]
            cmp r4, r3         @ Is element at r2 ≤ pivot?
            bgt 2f             @ If so, swap elements at r2 and r6,
            ldr r1, [r6]       @ Load previously first element in > side,
            str r4, [r6], #4   @ and postincrement r6,
            str r1, [r5, r2]   @ and save previous element at end of > side.
        2:  adds r2, #4        @ Increment offset.  Reached the end (>0)?
            ble 1b   @ Loop if ≤ 0 (either N && !V && !C, or !N && V && C)

            subs r1, r6, #8
            bl quirks               @ Recursively sort left partition.

            mov r0, r6
            mov r1, r5
            b 4b                  @ Tail-recursively sort right partition.

        3:  pop {r4, r5, r6, pc}

Fully commented source with Makefile and test C program at http://canonical.org/~kragen/sw/dev3/quicksort.S.