(Possibly counting sort) Designing O(N+n) algorithm that sorts i sequences

Question

This is one of the sample interview questions I have and it is:

There are i sequences of integers ranging [0,N-1] for N greater than or equal to 2. The total number of integers in all of the sequences is n (but sequences are not necessarily the same length). Design an O(N+n) algorithm that sorts i sequences and show that it is O(N+n). The output of algorithm should be k sorted sequences, not a single sorted sequence.

This question is pretty tricky since it is there are i sequences of integers with total number of elements equal to n. If it was a single array, I can just apply counting sort and do it in O(N+n) where n is number of input and N is the range. Is there an algorithm that can sort multiple sequences and output the sorted sequences not a single one? How can I solve this type of problem ?

Answer 1

variables:
input -- the array of array of integers to be sorted;
k -- the number of array
li -- the length of the array input[i]
n =l1 + ... + lk the total number of integer
N -- The integer to sort are in the range 0..N-1
count -- an matrix of size N*k+1 initially filled with k
output -- an array of the same format as input

total -- an array of length k initial filled with 0
x -- an individual input item, used within the algorithm
oldCount, i, j, b -- numbers used within the algorithm

Initialization

for i in [0,k-1]:
    for j in [0,li-1]
      x := input[i][j]
      if count[x][k]==k
      then count[x][k] := i;
           count[x][i] := (1,k);
      else 
         if count[x][k]== i
         then count[x][i] := (1,0)+count[x][i];
         else count[x][i] := (1,count[x][0]);
              count[x][k]== i;

computing the output:

for i in [0,..,N]
   b := count[i][k]
   while b<k do
      (c,b') := count[i][b];
      for j in [0,c-1]
         output[b][total[b]+j] := i;
      total[b] := total[b]+c;
      b:= b';

return output

Complexity:

The initialization loop is O(n)

The second loop is O(N+n) since the outmost for loop is run N times. And each times we enter the while loop we do 3 operation. And in the innermost for loop, each time we do an operation we change a new cell of the output, hence we do at most n operation in total (not each time but in total) for the innermost for