# 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"? Commented 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. Commented 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". Commented 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... Commented 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. Commented 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.