# Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays

$k = \Theta(n)$

The arrays consist only natural numbers $1$ to $n$

The sum of the length of all arrays = $\Theta(n)$

It should return the $k$ original arrays, each sorted on its own.

The running time should be at worst $\Theta(n)$. How is it even possible? There's something I must be missing because I have no idea how to approach this. The data I gave you is all the given data. Any ideas?

Using counting sort on each array won't work, for it will be $\Theta(n^2)$, but maybe a different approach using this method?

• Just for iterating over all arrays you need $\theta(n^2)$ operations, are you sure about your text ? – user80502 Dec 7 '17 at 10:23
• sorry I edit it, the change is "The sum of the length of all arrays = θ(n) " – MatanyaP Dec 7 '17 at 10:26
• No (explicit/$\omicron(n)$) limit on space? How is the problem/solution different from handling a single such array? – greybeard Dec 7 '17 at 12:01
• Cheeky (practical but impermissible) non-answer: radix sort all of the arrays. – Veedrac Dec 7 '17 at 12:25
• @greybeard There's no space limit to this question. the difference is you need to sort each array on its own, every element should stay at his original array. – MatanyaP Dec 8 '17 at 5:08

You can solve the issue by using some pointers. First, run counting sort algorithm on all arrays in $\Theta(n)$ (suppose all of them are in a set). In the meanwhile, when running the algorithm, set a pointer for each number of each array to the sorted index of that number.
Using this data structure, you will have $k$ sorted arrays at the end.