DS Self Check

Section 7.9 Self Check

Which of the following sort algorithms are guaranteed to be

O (n \log n)

even in the worst case?

Shell Sort
🔗
Incorrect! Shell sort is between $O (n)$ and $O (n^{2})$
Quick Sort
🔗
Incorrect! Quick sort can be $O (n \log n),$ but if the pivot points are not well chosen and the list is just so, it can be $O (n^{2}) .$
Merge Sort
🔗
Correct! Merge Sort is the only guaranteed $O (n \log n)$ even in the worst case. The cost is that merge sort uses more memory.
Insertion Sort
🔗
Incorrect! Insertion sort is $O (n^{2})$

Match each sorting method with its appropriate estimated comparisons.

Refer to previous sections of the chapter

Which sort should you use for best efficiency If you need to sort through 100,000 random items in a list?

You have attempted 1 of 3 activities on this page.