Insertion sort
sort.c:6
kernel
memory
cpu
source
a
int a[8]
0
4
1
9
2
17
3
j-1
31
4
j
12
5
i
26
6
5
7
20
31 > 12
so they trade places
31
12
sort.c
3
for
(
int
i =
1
; i < n; i++) {
4
int
j = i;
5
while
(j >
0
&& a[j-1] > a[j]) {
6
swap(&a[j-1], &a[j]);
7
j--;
locals
of sort()
i
int
5
j
int
4
n
int
8
a
int *
7
f
f
d
3
a
2
c
1
e
2
0
where a[0] is
While the one on the left is larger, they trade places,
and j follows the smaller value down.