From 8b3beceff2fea52488e675a04f12649ca248b78a Mon Sep 17 00:00:00 2001
From: Andreas Kapp Lindquist <alind24@student.sdu.dk>
Date: Mon, 29 Sep 2025 20:57:38 +0200
Subject: feat(insertionsort.s): Created insertionsorting algorithm

---
 src/insertionsort.s | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)
 create mode 100644 src/insertionsort.s

diff --git a/src/insertionsort.s b/src/insertionsort.s
new file mode 100644
index 0000000..af75a2a
--- /dev/null
+++ b/src/insertionsort.s
@@ -0,0 +1,69 @@
+# --------------------------------------------
+# 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 bytes
+#           rdx = index of key to sort by
+# OUTPUTS : rax = address for sorted A
+# CLOBBERS: none
+# NOTES   : Preserves all registers
+# --------------------------------------------
+.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, 1), %rdx), %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 %r15, $0                # Compare j with 0
+    jl end                      # Go to end if less than
+
+    movq ((%rdi, %r15, 1), %rdx), %r12  # Move A[j] into r12
+
+    cmp %r12, %rbx              # Compare A[j] with A[n]
+    jge end                     # Go to end if greater than or equal
+
+    movq %r15, %r14             # Duplicate r15 into r14
+    addq $1, %r14               # And add 1: j+1
+    movq %r12, ((%rdi, %r14, 1), %rdx)  # Move A[j] into 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 %rbx, ((%rdi, %r15, 1), %rdx)  # A[j+1] = x
+
+end:
+    # Restore registers
+    pop %r15
+    pop %r14
+    pop %r13
+    pop %r12
+    pop %rbp
+    pop %rbx
+
+    ret
+        
+    
-- 
cgit v1.2.3-70-g09d2