In-place "clumping-by-color" algorithm faster than sorting by color?

Question

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.

Answer 1

If I understand correctly, you're asking if preserving the locations of grouped values will give a speedup over reordering them, so for instance {2,2,2,1,1,1} would be left in place instead of rewriting the array as {1,1,1,2,2,2}. I would say no, because comparing-and-swapping is not slower than simply comparing in practice, and you probably need the same number of compares regardless.

I've done tests of different Dutch National Flag algorithms and found no variation in times between versions that do a lot of swaps vs. ones which do little (there was a period when that number was important, and a number of papers have been published on it). They all do the same number of comparisons, but the mechanics of moving elements into cache, etc. seems to make swaps almost free.

As greybeard notes, you're probably using the wrong Quicksort. Try the one described here: https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf . 2-way Quicksort is quadratic with duplicate values, for instance n duplicates will take o(n^2) since it will place all remaining values on one side of the pivot during each recursion.

Answer 2

If I understand correctly, your particular application makes moving items really expensive, so you'd like to preserve the location of values if possible. (Each item is a memory page ). For instance {2,2,2,1,1,1} would be left in place instead of rewriting the array as {1,1,1,2,2,2}. For instance, if every page had a different color, you would prefer to leave them all alone. For instance, if 2 pages had the same color, and all the other pages had a different color, ideally we would move only one or the other of the same-color pages to put them next to each other, and leave nearly all of the other pages alone -- { 7, 5, 16, 5, 3 } would change to either {7, 5, 5, 16, 3} or {7, 16, 5, 5, 3}.

Perhaps you could ("preserve starting location" algorithm):

• You have an array of N blocks with indexes 1...N, where each block has a color.
• Make a temporary array of (color, index) pairs. (in O(n) time)
• Sort that temporary array primarily by color and secondarily by the pointer, using any O(n log(n)) sorting algorithm. (in O(n log(n)) time)
• Do a linear scan through the temporary array, skipping all unique colors (in other words, dealing only with clusters of 2 or more identical colors, which the sort will have brought together):
  • Bring clusters of 2 or more identical colors together by leaving the first page of that color in place (smallest pointer-to-memory-page, which is the first of that color in both the "real" array of pages and also the first of that color in the temporary array), and moving the other pages with that color to the next consecutive locations, swapping with whatever used to be in those locations.

If the clusters are already grouped together, this algorithm should avoid moving any pages around. So it's "ideal" in the sense that the arbitrary assignment of colors to arbitrary numeric values is irrelevant and ignored. Alas, if there are 2 big clusters, and a few items of a thirds color squeezed between them -- a third color that has so many pages scattered elsewhere that there's not room for all the pages of that third color between those 2 clusters -- this algorithm doesn't quite finish the job, but it looks like it's possible to detect that situation while this algorithm is running.

Perhaps you could ("packing algorithm"):

• You have an array of N blocks with indexes 1...N, where each block has a color.
• Make a temporary array of (color, index) pairs. (in O(n) time)
• Sort that temporary array primarily by color and secondarily by the pointer, using any O(n log(n)) sorting algorithm. (in O(n log(n)) time)
• Do a linear scan through the temporary array
  • skip all unique colors (in other words, dealing only with clusters of 2 or more identical colors, which the sort will have brought together in the temporary array):
  • Pack clusters of 2 or more identical colors towards the beginning of the "real" array of pages; put the first cluster in consecutive group starting at the first "real" page; the second cluster immediately after that group, the third cluster immediately after the second cluster, etc. -- swapping with whatever used to be in those locations. (If the page "swapped out" belongs to some "later" cluster, update the "index" in the temporary array).

This "packing" algorithm swaps each page at most 2 times, so in terms of swaps it's a O(N) algorithm. When "swaps" are very slow compared to compares, this is faster than any O(N log(n) ) sorting algorithm. (This "packing" algorithm is clearly not ideal, moving some blocks unnecessarily just because clusters end up sorted by arbitrary numeric value. ).