Homework 8: Merge Sort and Quicksort
Due: 05/04 12:30pm
Name & Perm # (no partners allowed):
Reading: DS 13.2
\( \newcommand\bigO{\mathrm{O}} \)1. \( \)
Circle the big-O worst-case running time for sorting an array of \( n \) elements using
- (3 pts) Merge sort: \( \bigO(1) \quad \bigO(\log n) \quad \bigO(n) \quad \bigO(n \log n) \quad \bigO(n^2) \quad \bigO(n^2 \log n) \)
- (3 pts) Quicksort: \( \bigO(1) \quad \bigO(\log n) \quad \bigO(n) \quad \bigO(n \log n) \quad \bigO(n^2) \quad \bigO(n^2 \log n) \)
2. \( \)
Circle the big-O average-case running time for sorting an array of \( n \) elements using
- (3 pts) Merge sort: \( \bigO(1) \quad \bigO(\log n) \quad \bigO(n) \quad \bigO(n \log n) \quad \bigO(n^2) \quad \bigO(n^2 \log n) \)
(3 pts) Quicksort: \( \bigO(1) \quad \bigO(\log n) \quad \bigO(n) \quad \bigO(n \log n) \quad \bigO(n^2) \quad \bigO(n^2 \log n) \)
3. \( \)
Both merge sort and quicksort are divide-and-conquer algorithms.
(4 pts) What is the main idea behind divide-and-conquer?
(4 pts) Describe briefly how divide-and-conquer applies to merge sort.
(4 pts) Describe briefly how divide-and-conquer applies to quicksort.
(6 pts) Quicksort and merge sort are similar in that both are built on divide-and-conquer. Briefly highlight the differences between merge sort and quicksort.
(6 pts) Briefly describe the role of the pivot element in quicksort.