String Sorts

Question 1

How does key index counting work?

Answer 1

1. Compute frequency counts using a count array that is of size R + 1, using the key itself as an index. Therefore count[a[i] + 1]++
2. Create indices for distribution by cumulating, for r = 0 -> R, count[r+1] = count[r]. This tells us how many keys appear before r, and thus gives the index of r at a[]
3. Go through whole given aray. Access the count array using the char at the given array, add it to the index = count in the aux array and increment the count of the character
4. Copy aux over to original array

Question 2

How does LSD String sort work?

Answer 2

Consider characters from right to left
Perform key-indexed counting on each char of the strings
Each string needs to be the same length

Question 3

How does MSD work?

Answer 3

Create count array of size R + 2 and set values to 0
1. Count frequencies of first character
2. Transform the counts into indices
3. Distribute back
2. Sort subarrays corresponding to each character excluding first. Therefore sort(array, distributed index for character, lo + count[r+1] - 1, d + 1)

Question 4

What is the running time for LSD and MSD?

Answer 4

LSD: NW
MSD: N and Nw

Question 5

Where is the sweet spot for LSD and MSD?

Answer 5

LSD: short fixed-length strings
MSD: Random strings