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
71
72
|
# --------------------------------------------
# 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: none
# --------------------------------------------
.section .text
.globl insertion_sort
.type insertion_sort, @function
insertion_sort:
push %r8
push %r9
push %r10
push %r11
push %r14
push %r15
cmp $1, %rsi # n <= 1 -> done
jle done
movq $1, %r15 # i , start with 2nd element
loop:
# load A[i]
movq (%rdi,%r15,8), %r8 # pointer to key -> r8
movq (%r8,%rdx,8), %r9 # key -> r9
# set up index - 1 now
movq %r15, %r14 # j -> r14
decq %r14
inner_loop:
cmpq $0, %r14 # if j < 0 stop
jl insert_key
# load A[j]
movq (%rdi, %r14, 8), %r10 # pointer to key -> r10
movq (%r10, %rdx, 8), %r11 # key -> r11
# compare at A[i] with A[j]
cmpq %r11, %r9
jge 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 inner_loop
insert_key:
movq %r8, 8(%rdi,%r14,8)
# take the next number now
incq %r15 # i++
cmpq %rsi, %r15 # if i < n there are still numbers left to be sorted
jl loop
jmp done
done:
movq %rdi, %rax
pop %r15
pop %r14
pop %r11
pop %r10
pop %r9
pop %r8
ret
|