# How is the problem of sorting in contiguous runs called?

I am having a bit of brain fail and I can't remeber the name of the following problem (so I can find some literature around it...).

Given a sequence of values, sort it in a way that equal elements are compacted in runs (contiguous subsequences of identical elements).

For instance:

$$\{1, 2, 4, 2, 1, 3\} \rightarrow \{ 2, 2, 4, 3, 1, 1 \}$$

The runs are not otherwise sorted -- only equality comparison is required, not ordering; and they're compacted (there should not be two different runs containing equal elements).

• What about "counting"? – Raphael Jul 31 '15 at 15:55
• Why isn't the sorted array $\{1,1,4,2,2,3\}$? If the elements are not sorted the basic logic will be to check for the current element and swap all elements which are identical to it. – Sagnik Jul 31 '15 at 17:06
• @Raphael: it's not exactly counting -- elements in the same run can be different by other means; for instance, a sequence of "employees" arranged in runs by "year of birth". – peppe Jul 31 '15 at 18:43
• @Sagnik: sure, sorting would lead to a solution, however it requires an ordering (which is not necessary in the formulation of the problem above), and might possibly be less efficient... – peppe Jul 31 '15 at 18:45
• In distributed environments data is typically partitioned by a hash so that identical keys are stored on the same node; is that the type of situation you're thinking of? In that case the runs are on different nodes. The map phase in map-reduce is similar. – KWillets Jul 31 '15 at 19:39

## 1 Answer

Gopan et al. seem to define a more general problem and call it array partitioning .

The goals of array partitioning are twofold. First, we would like to isolate in separate groups [...] we partition an array so that each element whose index is equal to the value of any of the vari ables in the set is placed in a group by itself. [...]

[W]e partition each array $$A \in Array$$ by grouping together elements of $$A$$ for which all partitioning functions in $$\Pi_A$$ evaluate to the same values.

I have not dug into how their formal framework captures your problem and it may not even do so. Still, I think the general idea is close enough to use the word.

Come to think of it, Quicksort-style partitioning is related as well: you want to partition w.r.t. identify, in Quicksort we partition w.r.t. equivalence classes induced by some pivots.

1. A framework for numeric analysis of array operations by D. Gopan, T. Reps and M. Sagiv (2005) [preprint]