This assignment is to be done individually, without a partner. You may share ideas with others in the class, but you should turn in your own assignment.
1. On paper, sort 9, 8, 7, 6, 5, 4, 3, 2, 1 using Shellsort with increments {7, 3, 1}.
2. On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using merge sort.
3. On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using quicksort with the pivot in the first position.
4. Suppose that you have an array of n elements, containing only two distinct keys, true and false. Give an O(n) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space.
5. The choice of pivot for quicksort can dramatically affect its performance. Some common choices are: