**Java Programming**

1. Which of the following algorithms requires the most extra space when implemented as in the text?
   1. Insertion sort
   2. Mergesort
   3. Quicksort
   4. Shellsort
2. Which of the following algorithms runs in (NlogN) average time but quadratic worstcase time?
   1. Insertion sort
   2. Mergesort
   3. Quicksort
   4. Shellsort
   5. None of the above
3. Which of the following statements about sorting five elements is the strongest statement that is directly implied by the information theoretic lower bound?
   1. 6 comparisons are sufficient
   2. 6 comparisons are necessary and sufficient
   3. 7 comparisons are necessary
   4. 7 comparisons are sufficient
   5. 7 comparisons are necessary and sufficient
4. If the array is already sorted, which algorithm will perform best?
   1. Insertion sort
   2. Selection sort
   3. Merge sort
   4. Quick sort
   5. All will take equal time
5. For quicksort, what do i and j do when they see keys equal to the pivot?
   1. I stops, j stops
   2. I stops, j goe
   3. I goes, j stops
   4. I goes, j goes
   5. I and j alternate stopping and going