# Quick groupby - is this a well known algorithm?

I am interested in an algorithm that accepts an array that places identical elements contiguously but the array doesn't necessarily have to be sorted.

E.g. if input is

array = ["a", "a", "c", "b", "c"]

then output

groupby(array) = ["a", "a", "c", "c", "b"]

or

groupby(array) = ["c", "c", "a", "a", "b"]

etc. The point being the final order of the array isn't important; the only requirement is that identical elements have to be placed contiguously.

One algorithm that is inspired by quicksort is to pick an element, called it pivot, and divided the array into 3 segments with the first segment being all elements that equal pivot; and the other two begin those are "less than" and "greater than" pivot. Elements within each segment have to be placed contiguously.

The segmentation can be achieved in n time using a simple adaption of the pivoting in quicksort and then apply the algorithm recursively on the "less than" and "greater than" segment.

Is this algorithm well known and has a name? Or is it a novel algorithm?

• Isn't that just an ordinary quicksort with a "fat partition"? – Ilmari Karonen Oct 31 '17 at 0:49
• The algorithm doesn't need to sort. You don't have to use less than or greater than, actually any method that can break them into two groups is fine – xiaodai Oct 31 '17 at 2:54
• OK, but you still need to ensure that the elements with a given value always end up on the same side of the pivot, not split between the two sides, right? Still sounds (effectively) like sorting to me, but maybe I'm just missing something. Perhaps it would be clearer if you could provide a (pseudo)code version of your algorithm. – Ilmari Karonen Oct 31 '17 at 9:45
• @IlmariKaronen yes the method have to be determinstic – xiaodai Oct 31 '17 at 9:48

If you had a $o(n \log n)$ algorithm to solve your problem, you could combine it with a constant number of array scans to produce a $o(n \log n)$ time procedure to test whether the array contains a pair of identical elements, in contradiction with the well-known $\Omega(n \log n)$ lower bound on that problem.