Name:
(as it would appear on official course roster)
Umail address:	@umail.ucsb.edu	section 9am, 10am, 11am, 12pm
Optional: name you wish to be called if different from name above.
Optional: name of "homework buddy" (leaving this blank signifies "I worked alone"

h10: Mergesort and Quicksort

ready?	assigned	due	points
true	Thu 10/29 09:00AM	Mon 11/09 11:59PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN ON GRADESCOPE BEFORE THE DUE DATE,
There is NO MAKEUP for missed assignments;
in place of that, we drop the lowest scores (if you have zeros, those are the lowest scores.)

Reading: Mergesort and Quicksort, DS 13.2

(10 pts) Fill in the information in the header. The following are required to get the 10 "participation" points.
- Filling in your name and umail address.
Circle the big-O worst-case running time for sorting an array of n elements, using these algorithms:
1. (3 pts) Mergesort
  O(1) O(log n) O(n) O(n log n) O(n²) O(n² log n) O(n³)
2. (3 pts) Quicksort
  O(1) O(log n) O(n) O(n log n) O(n²) O(n² log n) O(n³)
Circle the big-O average case ("expected case") running time for sorting an array of n elements, using these algorithms:
1. (3 pts) Mergesort
  O(1) O(log n) O(n) O(n log n) O(n²) O(n² log n) O(n³)
2. (3 pts) Quicksort
  O(1) O(log n) O(n) O(n log n) O(n²) O(n² log n) O(n³)

Both Mergesort and Quicksort are divide-and-conquer algorithms.
1. (6 pts) What is the main idea behind divide-and-conquer?
2. (5 pts) Describe briely how the divide-and-conquer idea, as you explained in part (a), applies to Mergesort.
3. (5 pts) Describe briely how the divide-and-conquer idea, as you explained in part (a), applies to Quicksort.
4. (6 pts) Given that the way divide-and-conquer applies to Mergesort and Quicksort is similiar, briefly highlight the difference(s) between Mergesort and Quicksort.
(6 pts) Briefly describe the role of the pivot element in Quicksort.