# 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).

– Raphael
Jul 31, 2015 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. Jul 31, 2015 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". Jul 31, 2015 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... Jul 31, 2015 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. Jul 31, 2015 at 19:39

[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.