Question

1. You are given an array of integers, where different integers may have different number of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time.

2. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time. (Note that the desired order here is the standard alphabetical order; for example; a < ab < b.)

Answer 1

1. Since different integers in the array may have different number of digits, group the numbers in the array by number of digits and order each group using Radix Sort algorithm. Let G_i be the group containing i-digits integers, and say size of G_i is c_i. Assume there are total of k groups, then

1. Here also, we do almost the same thing as above. We first group the string according to the length and order each group using counting sort instead of radix sort.
2. for i ← maximum_length to 1
3.                perform counting sort on ith character. Include only the groups that have ith character.