<p>Even testing whether <span class="math-container">$n$</span> elements are distinct is known to require <span class="math-container">$\Omega(n \log n)$</span> time on a model with some pretty reasonable restrictions.  See, for example, 
<a href="https://www.sciencedirect.com/science/article/pii/089054019190034Y" rel="noreferrer">Anna Lubiw, András Rácz:
A Lower Bound for the Integer Element Distinctness Problem. Inf. Comput. 94(1): 83-92 (1991)</a>.</p>

CC BY-SA 4.0
2019-05-03T14:29:15.207Z
I always thought that hash sets had $O(1)$ insertion times. If I inserted $n$ elements into a hash set I would in the process be able to tell if any were equal. Does the model prevent me from using this technique to test distinctness in $O(n)$? (You might want to take a look at this paper, which claims that in the RAM model, integers can be sorted in $O(n \sqrt{\log \log n})$.) http://web.mit.edu/benmv/Public/thorup.pdf
Display Name
CC BY-SA 4.0
2019-05-03T16:17:05.190Z
Read the papers carefully to see what operations are allowed.   Algorithms faster than $O(n\log n)$ for sorting rely on assumptions on the sizes of the numbers, or use various bit tricks.
Jeffrey Shallit
CC BY-SA 4.0
2019-05-03T14:19:29.040Z
2019-05-03T14:19:29.040Z
Jeffrey Shallit
<p>Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is <span class="math-container">$O(n)$</span> because you can accomplish it by putting everything into a hashmap that maps keys to lists of equal elements.</p>

<p>The external memory model of computation is one where for an input size <span class="math-container">$N$</span> that's stored in "external memory," you can fit <span class="math-container">$M$</span> elements inside cache, and can transfer <span class="math-container">$B$</span> elements from cache to external memory per one slow I/O operation. All computation has to be done in cache.</p>

<p>The fastest sort in external memory is generally accepted to be an <span class="math-container">$O(N \log N)$</span> mergesort, even when the position in the output can be computed directly from the keys without any comparison. A surprising result shown in [1] is that, for practical[2] values of <span class="math-container">$B$</span> and <span class="math-container">$M$</span>, permuting the values in external memory based on indices that are already known is no faster than sorting them! (This is in sharp contrast to permutation in RAM, which is trivially <span class="math-container">$O(n)$</span>.)</p>

<p>I think grouping equal elements might be easier than permuting, because there are many permutations that would group equal elements. In a sense, if there is one "easy permutation" that groups equal elements, the algorithm could give you that instead of being forced to give you a specific permutation that may be very hard. Is this so? If it is so, what algorithm is known that could do it?</p>

<p>[1] <a href="https://pdfs.semanticscholar.org/05f5/c5521c69a87ed2fc32521312d85aeb1da874.pdf" rel="nofollow noreferrer">https://pdfs.semanticscholar.org/05f5/c5521c69a87ed2fc32521312d85aeb1da874.pdf</a></p>

<p>[2] This is actually not true for big (>4KB) elements on solid state drives, but it's commonly repeated and valid for many cases.</p>

<ds.algorithms><db.databases>
In external memory, is grouping equal elements easier than sorting?
Display Name
# In external memory, is grouping equal elements easier than sorting?

(Asked by: username_0 on 2019-05-03)

Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ because you can accomplish it by putting everything into a hashmap that maps keys to lists of equal elements.

The external memory model of computation is one where for an input size $N$ that's stored in "external memory," you can fit $M$ elements inside cache, and can transfer $B$ elements from cache to external memory per one slow I/O operation. All computation has to be done in cache.

The fastest sort in external memory is generally accepted to be an $O(N \log N)$ mergesort, even when the position in the output can be computed directly from the keys without any comparison. A surprising result shown in [1] is that, for practical[2] values of $B$ and $M$, permuting the values in external memory based on indices that are already known is no faster than sorting them! (This is in sharp contrast to permutation in RAM, which is trivially $O(n)$.)

I think grouping equal elements might be easier than permuting, because there are many permutations that would group equal elements. In a sense, if there is one "easy permutation" that groups equal elements, the algorithm could give you that instead of being forced to give you a specific permutation that may be very hard. Is this so? If it is so, what algorithm is known that could do it?

[1] <https://pdfs.semanticscholar.org/05f5/c5521c69a87ed2fc32521312d85aeb1da874.pdf>

[2] This is actually not true for big (>4KB) elements on solid state drives, but it's commonly repeated and valid for many cases.

**Tags:** ds.algorithms, db.databases

---

## 1 answers

### Answer by username_1 on 2019-05-03. Score: 5 | Accepted answer

Even testing whether $n$ elements are distinct is known to require $\Omega(n \log n)$ time on a model with some pretty reasonable restrictions. See, for example,
[Anna Lubiw, András Rácz:
A Lower Bound for the Integer Element Distinctness Problem. Inf. Comput. 94(1): 83-92 (1991)](https://www.sciencedirect.com/science/article/pii/089054019190034Y).

> **Comments:**
> **username_0**: I always thought that hash sets had $O(1)$ insertion times. If I inserted $n$ elements into a hash set I would in the process be able to tell if any were equal. Does the model prevent me from using this technique to test distinctness in $O(n)$? (You might want to take a look at this paper, which claims that in the RAM model, integers can be sorted in $O(n \sqrt{\log \log n})$.) http://web.mit.edu/benmv/Public/thorup.pdf  
> **username_1**: Read the papers carefully to see what operations are allowed.   Algorithms faster than $O(n\log n)$ for sorting rely on assumptions on the sizes of the numbers, or use various bit tricks.  

---

