Sorting Review

• Complete the following table with the properties of the indicated sorts. (Note that an "in-place" sort is a sort that doesn't require any additional space beyond the space required to store the input.)

  	Worst-Case Comparisons	Worst-Case Assignments	Worst-Case Time	Best-Case Time	Average Time	In place?	Stable?
  Selection Sort
  Insertion Sort
  Mergesort
  Quicksort

• Choose the best sorting algorithm for each of the following scenarios. You should choose from among selection sort, insertion sort, quicksort, and mergesort. In each case, justify your answer.

  • You need to sort a large list of unordered medical records by both date of birth and last name. After sorting, the list should be ordered by date of birth, with individuals who have the same date of birth ordered according to their last name. This will be accomplished by applying the same sorting algorithm twice: sorting first by name, then by date.

   

   

   

  • You are sorting shipping containers according to their scheduled departure time. The arrangement of the warehouse makes it impossible to reorder all of the containers at once. There is only room to swap one pair of containers at a time.

   

   

   

• Dr. Arugorizumu has recently submitted a paper claiming that he has developed a $\Theta(n)$ algorithm for within-two-sorting an array. He claims that, while the algorithm is not guaranteed to completely sort a sequence, it does guarantee that each key will end up no more than two positions away from its correct sorted location. Is this claim believable? Why or why not?

   

   

   

• The current programming assignment involves an optimization of the Mergesort algorithm that switches to insertion sort for small arrays. Develop a recurrence relation describing the best-case number of comparisons required by this modified Mergesort where $k$ is the threshold for switching. You should not assume that the input size is a power of 2.