1.
In practice, the number of memory movements also plays an important role in the run time of insertion sort. In which case do we have the worst-case number of memory operations? How does this relate to the number of comparisons?
Section 3.3 Insertion Sort
Insertion sort is a simple sorting algorithm that mimics the way we sort small collections of things in our daily lives. Assume that we are given an array of \(n\) elements that are to be sorted. Insertion sort subdivides the array into two parts: A first part containing already sorted elements and the unsorted rest. In every step, insertion sort takes one element \(x\) from the unsorted part (it doesn't matter which one, typically one takes the first). 
Then, it inserts at the right spot in the sorted part and moves the remaining sorted elements greater than the inserted element one up. 
This step is repeated \(n-1\) times until the unsorted part is empty. Initially, the sorted part consists of just the first element of the array and the rest of the array constitutes the unsorted part.
Running time.
When counting the number of comparisons, the worst-case running time of insertion sort is \(O(n^2)\) because if the case that the input is already sorted, we need \(i-1\) comparisons when inserting the \(i\)-the element. This sums up to \(1+2+\cdots+n=\sum_{i=1}^{n-1}i=\frac{n(n-1)}2\) comparisons.
Finally, the following RISC-V code implements insertion sort for integer arrays:
.text
# a0 address of first element
# a1 address of element past the last
insertsort:
addi t0, a0, 4
outer_loop:
beq t0, a1, outer_end
mv t1, t0
inner_loop:
beq t1, a0, inner_end
lw t2, 0(t1)
lw t3, -4(t1)
blt t3, t2, inner_end
sw t2, -4(t1)
sw t3, 0(t1)
addi t1, t1, -4
j inner_loop
inner_end:
addi t0, t0, 4
j outer_loop
outer_end:
ret
