@R0 contains the low address
@R1 contains the high address
@We assume partition based on last element as pivot
@A better implementation would do a median-of-3 pivot
@to prevent quicksort degenerating from O(n*log(n)) to O(n^2)
@Median-of-3 would also allow us to optimize away 2 bounds checks
@Return position of pivot in R0

_hoare_partition:

  @ save array bounds
  MOV R5, R0
  MOV R6, R1

  @ save pivot value
  MOV R2, R1
  LDR R2, [R2]

  @ i = lo - 1
  SUB R0, R0, #4

  @ loop forever (until partitioning is done)
  _partition_loop_forever:

    @ do {i = i + 1 } while A[i] < pivot
    _first_partition_loop:

      @ bounds check
      @ if (i == right) break
      CMP R0, R6
      BEQ _second_partition_loop

      ADD R0, R0, #4
      LDR R3, [R0]
      CMP R3, R2
      BLT _first_partition_loop

    @ do {j = j - 1} while A[j] > pivot

    _second_partition_loop:

      @ bounds check
      @ if (j == left) break
      CMP R1, R5
      BEQ _end_partition

      SUB R1, R1, #4
      LDR R4, [R1]
      CMP R4, R2
      BGT _second_partition_loop

    @ if i >= j  then return j

    CMP R0, R1
    BGE _end_partition

    @ swap A[i] with A[j]
    STR R3, [R1]
    STR R4, [R0]

    BAL _partition_loop_forever

  _end_partition:

    @ swap last element (pivot) into correct place
    ADD R1, R1, #4
    LDR R7, [R6]
    LDR R8, [R1]
    STR R7, [R1]
    STR R8, [R6]

    @ return position of pivot in R0 (Linux ABI-compatible)
    MOV R0, R1
    @ return from function
    MOV PC, LR
                                                                                                                                                                                                  22,11         16