### NAMES:

### LOGINS:

### PRECEPTS:

###
COS 226 Exercises on String Sort

*References: Section 5.1 in Algorithms, 4th edition *

**1. **
Sort the 16 names below using LSD string sort, algorithm 5.1 in the book.
Show the result (by listing the 16 full words) of each of the four stages of the sort.

Stage 0 Stage 1 Stage 2 Stage 3 Stage 4
------- ------- ------- ------- -------
John
Jane
Alex
Eric
Dave
Gabe
Will
Nick
Jada
Jake
Nish
Luke
Kyle
Rick
Yuan
Emma

**2. **
Show the contents of the array after one partitioning step in 3-way string quicksort
of the following 16 names. Use the 3-way partitioning scheme using algorithm
5.3 in the book.

After partitioning
Input on the J in John
------- ------------------
John
Jane
Alex
Eric
Dave
Gabe
Will
Nick
Jada
Jake
Nish
Luke
Kyle
Rick
Yuan
Emma