You are given a set {s1 , s2 , ... , sn} of strings. Each string si is over the alphabet {a, b, c, ... , z }. Let ki = | si | denote the length of si , and let m = n i=1 ki .

(a) [10] Give detailed pseudocode for an iterative algorithm (a modification of Radix sort, do not use a recursive approach) that runs in O(m) time to lexicographically sort all the strings. Note that if your algorithm runs in (n * Max{k1 , k2 , ... , kn} ), this is not a correct solution to this problem and you will not get any marks for this question. As an example for the requirement of sorting lexicographically: the string rock is smaller than rocket which is smaller than rot. You can assume that the jth symbol of a string can be accessed in O(1) time.

(b) [5] Prove that your algorithm takes at most O(m) time.