Sorting m sets of total O(n) elements in O(n)

Question

Suppose we have m sets S1,S2,...,Sm of elements from {1...n} Given that m=O(n) , |S1|+|S2|+...+|Sm|=O(n) sort all the sets in O(n) time and O(n) space.

I was thinking to use counting sort algorithm on each set. Counting sort on each set will be O(S1)+O(S2)+...+O(Sm) < O(n) and because that in it's worst case if one set consists of n elements it will still take O(n).

But will it solve the problem and still hold that it uses only O(n) space?

Answer 1

Your approach won't necessarily work in O(n) time. Imagine you have n sets of one element each, where each set just holds n. Then each iteration of counting sort will take time Θ(n) to complete, so the total runtime will be Θ(n²).

However, you can use a modified counting sort to solve this by effectively doing counting sort on all sets at the same time. Create an array of length n that stores lists of numbers. Then, iterate over all the sets and for each element, if the value is k and the set number is r, append the number r to array k. This process essentially builds up a histogram of the distribution of the elements in the sets, where each element is annotated with the set that it came from. Then, iterate over the arrays and reconstruct the sets in sorted order using logic similar to counting sort.

Overall, this algorithm takes time Θ(n), since it takes time Θ(n) to initialize the array, O(n) total time to distribute the elements, and O(n) time to write them back. It also uses only Θ(n) space, since there are n total arrays and across all the arrays there are a total of n elements distributed.

Hope this helps!