Binning a set into subsets deterministically

Question

I have an unordered set of n unique, positive integers. I want to partition it into ceil(n / k) unordered sets of up to k numbers (k << n) in a deterministic way (I want to get a sequence of the same ceil(n / k) output sets without depending on a fixed order of the input).

Is there a way to do so that has superior algorithmic complexity to sorting the set and partitioning the resulting sequence?

Answer 1

Here is an approach whose average performance is O(n), which beats O(n log(n)).

Pick m with r < m < n, where r = ceil(n / k) is the number of buckets. For each number, hash it and stick it into one of m bags. (I'm deliberately using bags vs buckets, with bags smaller.) This is a O(n) task. Now we can construct our r buckets by running through the m bags, and when fill a bucket up up, we quickselect a single one of the m bags. Running through those bags is O(m), putting them into the r is O(n), and splitting the r-1 bags on a boundary with quickselect is O(r * (n/m)) which is definitely contained within O(n).