# Homework 8: Merge Sort and Quicksort

Due: 05/04 12:30pm

Name & Perm # (no partners allowed):

$$\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.

Author: Instructor: Mehmet Emre

Created: CS 32 Spring '22

The material for this class is based on Prof. Richert Wang's material for CS 32