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?
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).
