Suppose we are given an array $a\colon[n]\to[m]$ of length $n$ (and each entry is between 1 and m). We will denote the $i$th entry of the array as $a[i]$.

Task: Permute the array $a$ in-place so that the elements of the same value are grouped together. To be explicit, the final array $a$ needs to satisfy $$a[i] = a[j]\implies \forall i < k < j, a[k] = a[i].$$ Here we assume the randomized word RAM model with $\log m$ bit wide words (take $m > n$).

For the purposes of this question in-place means using $\mathrm{polylog}(n)$ words of space on top of the mutable array $a$, which can be changed arbitrarily but at the end of the algorithm must be a permutation of the original array.

Is there an in-place algorithm known with running time $o(n\log n / \log \log n)$?

Does the integer sorting literature offer anything for this?

  • 1
    $\begingroup$ Observation: we can use 1 extra bit of space per element without changing the asymptotics. Step 1: partition $a$ based on each elements lowest bit. Duplicate elements obviously end up in the same partition, so grouping is not violated. Step 2. Apply algorithm to each partition individually using the lowest bit as extra storage as desired. Step 3. Restore lowest bits for each partition. Observation 2: we can repeat this process an arbitrary (but constant) amount of times for $O(1)$ auxiliary space per element. $\endgroup$ – orlp Jul 17 '19 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.