$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?

  • $\begingroup$ Just for iterating over all arrays you need $\theta(n^2)$ operations, are you sure about your text ? $\endgroup$
    – user80502
    Dec 7 '17 at 10:23
  • $\begingroup$ sorry I edit it, the change is "The sum of the length of all arrays = θ(n) " $\endgroup$
    – MatanyaP
    Dec 7 '17 at 10:26
  • $\begingroup$ No (explicit/$\omicron(n)$) limit on space? How is the problem/solution different from handling a single such array? $\endgroup$
    – greybeard
    Dec 7 '17 at 12:01
  • $\begingroup$ Cheeky (practical but impermissible) non-answer: radix sort all of the arrays. $\endgroup$
    – Veedrac
    Dec 7 '17 at 12:25
  • $\begingroup$ @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. $\endgroup$
    – 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.

  • $\begingroup$ tnx, sorry but I didn't quite understand the part when you set pointers. can you elaborate? you point each number to its index in the counter? $\endgroup$
    – MatanyaP
    Dec 7 '17 at 11:44
  • $\begingroup$ @MatanyaP Yes. Indeed, you can see all these arrays as a single array. Then sort them using counting sort algorithm. When you run the algorithm, set a pointer from each element of each array to its index in that universal sorting. In this way, you have sorted the sub arrays. $\endgroup$
    – OmG
    Dec 7 '17 at 12:14
  • $\begingroup$ Note that you need multiple counts per bucket, and to avoid allocating it all in advance that means you probably want to make each bucket a dynamically-sized hash map. Not all that cheap on real hardware ;). $\endgroup$
    – Veedrac
    Dec 7 '17 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.