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 MIPS code implements insertion sort for integer arrays:
.text
# $a0 address of first element
# $a1 address of element past the last
insertsort:
addiu $t0 $a0 4
outer_loop:
beq $t0 $a1 outer_end
move $t1 $t0
inner_loop:
beq $t1 $a0 inner_end
lw $t2 ($t1)
lw $t3 -4($t1)
slt $t4 $t3 $t2
bnez $t4 inner_end
sw $t2 -4($t1)
sw $t3 ($t1)
addiu $t1 $t1 -4
b inner_loop
inner_end:
addiu $t0 $t0 4
b outer_loop
outer_end:
jr $ra
