An algorithm for k-way array partitioning

Question

I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s_1, s_2, \cdots, s_{n-1}$ into $n$ subsequences, where subsequence $i$ all have values in the range of $[s_i, s_{i + 1})$ (let $s_0 = -\inf, s_n = \inf$).

My question is: how to implement this efficiently, preferably in place?

I can't even figure out how to do it out of place, other than allocating $n$ dynamic sized arrays and finally concatenating them together. In the case of single splitter, we can successively push the values smaller and larger than the splitter to the two ends respectively, but for more splitters, I don't know how to do it efficiently.

Answer 1

I can't even figure out how to do it out of place, other than allocating n dynamic sized arrays and finally concatenating them together.

Which is the approach used by the explanation in Wikipedia, so it's not necessarily a bad one.

My question is: how to implement this efficiently, preferably in place?

I assume you know how to do a quicksort partition. To do the multi-way split in place, you can turn it into a series of quicksort partitions.

# Splitters are sorted
# min and max indices are inclusive
multipartition(array A, int Amin, int Amax, array Splitters, int Smin, int Smax):
 if Amax <= Amin:
 return
 if Smax < Smin:
 inner_sort(A, Amin, Amax)
 else:
 Smid = Smin + (Smax - Smin) / 2
 split_idx = partition(A, Amin, Amax, Splitters[Smid])
 multipartition(A, Amin, split_idx - 1, Splitters, Smin, Smid - 1)
 multipartition(A, split_idx + 1, Amax, Splitters, Smid + 1, Smax)

I assert that this is as efficient as the non-in-place approach based on binary search given in the Wikipedia article, because each element of A will take place in $\log(|\text{Splitters}|)$ calls to partition, which is linear time.