1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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
|