Answer TRUE or FALSE.

Mergesort (as the code is written in this chapter) is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

• True
• False

You must merge 2 sorted lists of size $m$ and $n$, respectively. The number of comparisons needed in the worst case by the merge algorithm will be:

• $m+n-1$
• $mn$
• $\max(m,n)$
• $\min(m,n)$
• $m+n$

What is the most complicated part of the Mergesort algorithm?

• Merging the sorted halves back together
• Finding the midpoint
• Partitioning the array
• Achieving the base case

In which cases are the time complexities the same for Mergesort?

• Worst, Average and Best
• Worst and Best
• Best and Average
• Worst and Average

The order of the input records has what impact on the number of comparisons required by Mergesort (as presented in this chapter)?

• None
• There is a constant factor difference
• There is a big difference, the asymptotic running time can change

What is the worst-case time for Mergesort to sort an array of $n$ records?

• $O(n \log n)$
• $O(n)$
• $O(\log n)$
• $O(n^2)$
• $O(n^n)$

What is the running time of Mergesort when the input is an array where all record values are equal?

• $O(n \log n)$
• $O(n^2)$
• $O(\log n)$
• $O(n ^ n)$
• $O(n)$

When is Mergesort a good choice for sorting an array?

• We need a reasonably fast algorithm with a good worst case cost
• Each record requires a large amount of memory
• Each record requires a small amount of memory
• The processor speed is fast
• The array contains many records
• We need good best-case running time
• None of these situations

In the worst case, the total number of comparisons for Mergesort is closest to: - [x] $n \log n$ - [ ] $n$ - [ ] $n^2$ - [ ] $n^2/2$

The array-based implementation for Mergesort uses how many arrays?

• $2$
• $1$
• $n$
• $\log n$

Answer TRUE or FALSE.

Quicksort (as the code is written in this chapter) is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

• True
• False

On average, how many comparisons does Quicksort require to sort 1000 records (to the nearest 1000 comparisons)?

If it takes a given computer one second on average to run Quicksort on an array of 1000 records, how long (to the nearest thousand seconds) will it take to run Quicksort on 1,000,000 records?

(You know from this statement that the machine can do about 10,000 comparisons per second. To get the answer, you first need to compute about how many total comparisons 1,000,000 records will require.)

In which cases are the time complexities the same for Quicksort?

• Best and Average only
• Worst and Best only
• Worst and Average only
• Worst, Average, and Best

The order of the input records has what impact on the number of comparisons required by Quicksort (as presented in this chapter)?

• There is a big difference, the asymptotic running time can change
• None
• There is a constant factor difference

What is the worst-case cost for Quicksort to sort an array of n elements?

• $O(n^2)$
• $O(n)$
• $O(\log n)$
• $O(n \log n)$

What is the best-case cost for Quicksort to sort an array of n elements?

• $O(n \log n)$
• $O(n)$
• $O(\log n)$
• $O(n^2)$

A disadvantage of Quicksort is:

• Its worst-case running time is $O(n^2)$
• It needs an extra array for auxilliary storage
• It is stable
• Its average-case running time is $O(n^2)$

(For the version of the algorithm as presented in this chapter) What is the running time of Quicksort when the input is an array where all record values are equal?

• $O(n^2)$
• $O(n)$
• $O(\log n)$
• $O(n \log n)$
• $O(n ^ n)$

Quicksort’s worst-case case cost is $O(n^2)$ and its average-case cost is $O(n \log n)$. This means that the fraction of input cases with cost $O(n^2)$ must:

• Drop as $n$ grows
• Never happen
• Happen only once
• Be less than half
• Be less than 1 in $n$
• Be less than 1 in $n!$

What is the worst-case cost for Quicksort’s partition step?

• $O(n)$
• $O(n^2)$
• $O(\log n)$
• $O(n \log n)$

When selecting a pivot value, a simple thing to do is to always pick from the same place in the partition. If we use this approach, does it matter whether we always pick from the first position in the partition, the last position in the partition, or the middle position in the partition?

• It is better to pick the middle value
• It is better to pick the first value
• It is better to pick the last value
• It doesn’t really matter, they are all equally good or bad

When is Quicksort a good choice for sorting an array?

• In most standard situations where you want to sort many records
• Each record requires a large amount of memory
• Each record requires a small amount of memory
• The processor speed is fast
• We need a reasonably fast algorithm with a good worst case

Answer TRUE or FALSE.

Selection sort is generally faster than the Bubble sort on the same input.

• True
• False

How are Selection sort and Quicksort similar?

• They can both swap non-adjacent records
• They are both $O(n \log n)$ sorts
• They both use divide-and-conquer
• Both have quadratic average case time

(For the implementations as presented in this chapter:) Which of the following sorts is not stable?

• Quicksort
• Insertion sort
• Mergesort

What do we call the property of a sorting algorithm that gaurantees that records with the same key value occur in the same order in the sorted list as in the original, unsorted list?

• Stable
• Consistent
• External
• Linear

A person sorting a hand of cards might reasonably use which sorting algorithm?

• Insertion sort
• Bubble sort
• Quicksort
• Mergesort

Consider what happens if someone accidently calls sort on a file that is already sorted. Which of the following sorting methods will be the most efficient if the input is already in sorted order?

• Insertion sort
• Bubble sort
• Selection sort
• Mergesort

Which of the following sorting methods will be best if the number of swaps done is the only measure of efficiency?

• Selection sort
• Bubble sort
• Insertion sort
• Mergesort
• Quicksort

Which of the following sorting algorithms has a worst case complexity of $O(n \log n)$?

• Mergesort
• Bubble sort
• Selection sort
• Insertion sort
• Quicksort

When Mergesort merges two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, it requires how many comparisons in the worst case?

• $m+n-1$
• $m+n$
• $m$
• $n$
• $n+1$
• $O(\log m + \log n)$
• $O(\log m + \log n + 1)$