# --------------------------------------------
# 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 = number of coordinates n
#           rdx = index of key to sort by
# OUTPUTS : rax = address for sorted A
# CLOBBERS: rax, rdx, rdi, rsi, r8, r9, r10, r11
# --------------------------------------------
.section .text
.globl insertion_sort 
.type insertion_sort, @function
insertion_sort:
    # save
    push %r14
    push %r15


    cmp $1, %rsi                    # if n <= 1 jmp done
    jle .insertion_sort_done

    # set up i
    movq $1, %r15                   # i , start with 2nd element

.insertion_sort_loop:
    # load A[i]
    movq (%rdi,%r15,8), %r8         # pointer to key -> r8
    movq (%r8,%rdx,8), %r9          # key -> r9

    # set up j
    movq %r15, %r14                 # j -> r14
    decq %r14

.insertion_sort_inner_loop:
    cmpq $0, %r14                   # if j < 0 stop and insert the key
    jl .insertion_sort_insert_key

    # load A[j]
    movq (%rdi, %r14, 8), %r10      # pointer to key -> r10
    movq (%r10, %rdx, 8), %r11      # key -> r11


    # compare A[i] with A[j]
    cmpq %r11, %r9
    jge .insertion_sort_insert_key  # if A[i] >= A[j] stop

    # if A[i] < A[j]
    movq %r10, 8(%rdi, %r14, 8)     # pointer to key of j -> A[j+1]

    decq %r14                       # move to j - 1
    jmp .insertion_sort_inner_loop


.insertion_sort_insert_key:
    movq %r8, 8(%rdi,%r14,8)

    # take the next number
    incq %r15                       # i++
    cmpq %rsi, %r15                 # if i < n there are still numbers left to be sorted
    jl .insertion_sort_loop
    jmp .insertion_sort_done

.insertion_sort_done:
    movq %rdi, %rax

    # retrieve
    pop %r15
    pop %r14
    ret