1. Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort.

2. What is the running time of insertion sort if all elements are equal?

3. Suppose we exchange elements a[i] and a[i+k], which were originally out of order. Prove that at least 1 and at most 2k - 1 inversions are removed.

4. Show the result of running Shellsort on the input 9, 8, 7, 6, 5, 4, 3, 2, 1 using the increments {1, 3, 7}.