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
  Heapsort

• Choose the best sorting algorithm for each of the following scenarios. You should choose from among selection sort, insertion sort, quicksort, mergesort and heapsort. 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 an algorithm for constructing a balanced binary search tree from a collection of unordered keys in $\Theta(n)$ time. Is this claim believable? Why or why not?

• The textbook describes an optimization of the Mergesort algorithm that involves switching to insertion sort for small arrays. Develop a recurrence relation describing the exact 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.