In-place “clumping-by-color” algorithm faster than sorting by color?

I don't know what to call this, so I'm calling it "clumping by color".

Suppose I have an array of length $n$ where each of the items has one of $m$ "colors". I'd like to permute the elements so that all the items are "clumped" together with other items of the same color. That is, in the final array ordering

$$x_0, x_1, \cdots x_{n-1}$$

if $x_i \neq x_{i+1}$, then $\forall j \lt i,\, x_j \neq x_{i+1}$ and $\forall k \gt i+1,\, x_k \neq x_i$.

I know I can solve this "in place" in time $O(n \log n)$, and additional space $O(\log n)$ because I can use an in-place sort (like introsort to produce a permutation that satisfies the clumping constraint, but I'm hoping for at least a smaller constant factor by taking advantage of the fact that I don't care about the order of the colors.

Right now we have an $O(n^2)$ algorithm that is analogous to selection sort

i = 1
while i < n:
pivot = x[i-1]
while (i < n) and (x[i] == pivot):
i = i+1

for j = i+1 to n:
if x[j] == pivot:
swap(x[i], x[j])
i = i+1


We've also tried a quicksort, which works a little better when the number of colors is large and mostly sorted by the arbitrary integer values assigned to the colors, but worse when the number of colors is small. It would seem that something like counting sort might be a desirable way to go but (a) we really need this to be in-place (the colors actually represent pages, we're doing the clumping to avoid tlb misses, and out-of-place sorts (like counting sort) are just going to make the tlb thrashing worse.) And (b) while the number of colors in an array of length $n$ obviously can't be larger than $n$, the number of colors in the "universe" is much larger (something like $2^{52}$ on a machine with 64-bit virtual addresses). And (c) part of the reason quicksort is often worse than our $O(n^2)$ algorithm is that it sorts the colors by their arbitrary numeric value, which wastes time.

• The word you are looking for may be clustering. Picking a quicksort implementation, be sure to use one that doesn't degenerate when the pivot value occurs many times - look for/into three-way-partitioning and dual pivot. It would seem advantagous to be able to specify an expected cluster size to shift the cut-off for "recursion". – greybeard Jun 8 '15 at 5:45