# --------------------------------------------
# FUNCTION: insertion_sort
# 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 = length of A in 64 bit chunks
#           rdx = index of key to sort by
# OUTPUTS : rax = address for sorted A
# CLOBBERS: none
# NOTES   : Preserves all registers. Recursive psudocode taken from 
#           https://en.wikipedia.org/wiki/Insertion_sort
# --------------------------------------------
.section .text
.globl insertion_sort 
.type insertion_sort, @function
insertion_sort:
    # Save registers
    push %rbx
    push %rbp
    push %r12
    push %r13
    push %r14
    push %r15

    cmp $0, %rsi                # Check if length of array is zero
    je end                      # Jump to end if it is

    push %rsi                   # Save array size
    subq $1, %rsi               # Decrease size of array
    call insertion_sort         # Sort recursively
    pop %rsi                    # Restore array size

    movq (%rdi, %rsi, 8), %rbp  # Save address at A[n] in rbp
    movq (%rbp, %rdx, 8), %rbx  # Save value of A[n] in rbx

    movq %rsi, %r15             # Save copy of n in r15
    subq $1, %r15               # Make r15 = n-1 = j

while:
    cmp $0, %r15                # Compare j with 0
    jl end_while                # Go to end if less than

    movq (%rdi, %r15, 8), %rbp  # Save address at A[j] to rbp
    movq (%rbp, %rdx, 8), %r12  # Move value at A[j] into r12

    cmp %r12, %rbx              # Compare A[j] with A[n]
    jge end_while               # Go to end if greater than or equal

    movq %r15, %r14             # Duplicate r15 into r14
    addq $1, %r14               # And add 1: j+1
    movq (%rdi, %r14, 8), %rbp  # Save address of A[j+1] in rbp
    movq %r12, (%rbp, %rdx, 8)  # Move value at A[j] into value at A[j+1]
    
    subq $1, %r15               # j = j - 1

    jmp while                   # Go back to start of loop

end_while:
    addq $1, %r15               # j = j + 1
    movq (%rdi, %r15, 8), %rbp  # Move address at A[j] into rbp
    movq %rbx, (%rbp, %rdx)     # A[j] = x

end:
    # Restore registers
    pop %r15
    pop %r14
    pop %r13
    pop %r12
    pop %rbp
    pop %rbx

    ret