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
Shell sort is between \(O(n)\) and \(O(n^2)\)
Quick Sort
Quick sort can be \(O(n \log n)\text{,}\) but if the pivot points are not well chosen and the list is just so, it can be \(O(n^2)\text{.}\)
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
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 of activities on this page.