1 files changed, 70 insertions, 0 deletions
diff --git a/src/insertionSort.s b/src/insertionSort.s
new file mode 100644
index 0000000..7badac0
--- /dev/null
+++ b/src/insertionSort.s
@@ -0,0 +1,70 @@
+# --------------------------------------------
+# 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