# --------------------------------------------
# FUNCTION: qsort
# PURPOSE : Sorts array A, with references to arrays A_i,
#           based on the given key in A_i,
#           address and size of A.
# INPUTS  : rdi = address for A
#           rsi = number of coordinates n
#           rdx = index of key to sort by
# OUTPUTS : rax = address for sorted A
# CLOBBERS: none
# --------------------------------------------
.section .text
.globl qsort
.type qsort, @function
qsort:
    pushq %r12
    pushq %r13
    pushq %r14
    pushq %rbx

    cmp $1, %rsi
    jle .qsort_done

    call hoare_part
    movq %rax, %r12             # r8 = partition
    movq %rdi, %r13             # r13 = original array pointer
    movq %rsi, %r14             # r14 = original n
    movq %rdx, %rbx             # rbx = column index

    # --- left recursion ---
    movq %r13, %rdi
    movq %r12, %rsi             # n = p
    movq %rbx, %rdx             # restore column
    call qsort

    # --- right recursion ---
    leaq 1(%r12), %rax          # rax = p + 1
    leaq (%r13, %rax, 8), %rdi  # rdi = A + (p + 1)
    movq %r14, %rsi             # rsi = original n
    subq %rax, %rsi             # rsi = n - (p + 1)
    movq %rbx, %rdx             # restore column
    call qsort

.qsort_done:
    movq %r13, %rax
    popq %rbx
    popq %r14
    popq %r13
    popq %r12
    ret

# --------------------------------------------
# FUNCTION: hoare_part
# PURPOSE : 
# INPUTS  : rdi = address for A
#           rsi = number of coordinates n
#           rdx = index of key to sort by
# OUTPUTS : rax = Returns the partition index
#           for quicksort.
# --------------------------------------------
.globl hoare_part
.type hoare_part, @function
hoare_part: 
    pushq %r12
    pushq %r13

    movq $-1, %r8               # i = -1
    movq %rsi, %r9              # j = arr.len
    movq (%rdi), %r10           # pivot = &arr[0]
    movq (%r10, %rdx, 8), %r11  # value of pivot
    pushq %r11

.hoare_loop:
# increment i
.hoare_Li:
    addq $1, %r8

    cmpq %r9, %r8
    jge .hoare_done

    movq (%rdi, %r8, 8), %r13
    movq (%r13, %rdx, 8), %r12  # value of arr[i]

    cmpq %r11, %r12             # if arr[i] < pivot
    jl .hoare_Li
    
# decrement j
.hoare_Lj:
    subq $1, %r9

    cmpq $0, %r9
    jl .hoare_done

    movq (%rdi, %r9, 8), %r13
    movq (%r13, %rdx, 8), %r12  # value of arr[j]

    cmpq %r11, %r12             # if arr[j] > pivot
    jg .hoare_Lj

    # check crossing
    cmpq %r9, %r8               # if arr[i] > arr[j]
    jge .hoare_done
    
    # swap a[i] and a[j]
    movq (%rdi, %r8, 8), %r12
    movq (%rdi, %r9, 8), %r13
    movq %r13, (%rdi, %r8, 8)
    movq %r12, (%rdi, %r9, 8)

    jmp .hoare_loop

.hoare_done:
    popq %r11
    popq %r13
    popq %r12
    movq %r9, %rax
    ret