refactor(insertionsort.s): Renamed to insertion_sort.s

1 files changed, 74 insertions, 0 deletions

diff --git a/src/insertion_sort.s b/src/insertion_sort.s
new file mode 100644
index 0000000..490d56b
--- /dev/null
+++ b/src/insertion_sort.s
@@ -0,0 +1,74 @@
+# --------------------------------------------
+# 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
+
+    subq $1, %rsi               # Decrease size of array
+    push %rsi
+    call insertion_sort         # Sort recursively
+    pop %rsi
+
+    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
+        
+