Comment on page

# 35.5 Exercises

- 1.If we use counting sort to sort all 61B students by the number of siblings they have, how long will the counting array be? Let$N$be the total number of students and$M$be the maximum number of siblings a student has.
- 2.When performing a radix sort like LSD or MSD, which of the following sorting algorithms could we use for each digit?
- Counting sort
- Heapsort
- Mergesort
- Selection sort

- 3.If we're sorting N lowercase english strings using MSD sort, what is the maximum number of subproblems after considering only the the most significant digit?

- 1.What are some advantages of counting sort over quicksort?
- 2.Why do we use LSD over counting sort?
- 3.If we use MSD radix sort, we start with a single problem of size N, where N is the number of strings. Depending on the results on the most significant digit, we end up with a larger number of smaller subproblems, i.e. we're doing some divide and conquer. In the worst case, we end up with only one subproblem, also of size N. When does this happen?

Many correct answers, but some advantages include:

- For sufficiently large N, counting sort is faster (since it is linear as compared to N log N).
- Counting sort is stable, since we scan from the first element to the last.
- Counting sort doesn't use comparisons between elements, which might be useful if elements are not comparable.

Counting sort is technically faster than LSD, since counting sort doesn't require splitting up items by digits/letters. However, counting sort can require extremely large amounts of memory in some cases (for example, when sorting

`String`

s, you need one entry in an array for every possible `String`

). Last modified 7mo ago