An algorithm for k-way array partitioning
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 &lt;= Amin:
        return
    if Smax &lt; 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.