Given an array A of n integers in the range [0, n 2 −1], describe a simple method for sorting A in O ( n ) time.   Let S 1, S 2, . . . , Sk be k different sequences whose elements have integer keys in...

Given an array
A
of
n
integers in the range [0,n2 −1], describe a simple

method for sorting
A
in
O(n) time.

Let
S1,S2, . . . ,Sk
be
k
different sequences whose elements have integer

keys in the range [0,N
−1], for some parameter
N
≥ 2. Describe an algorithm

that produces
k
respective sorted sequences in
O(n+N) time, were

n
denotes the sum of the sizes of those sequences.