diff options
Diffstat (limited to '')
| -rw-r--r-- | src/insertionsort.s | 69 |
1 files changed, 69 insertions, 0 deletions
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 + + |