# Efficient algorithm for joining sieves

I'm trying to find an efficient algorithm for the following algorithm.

I have a sequence consisting of lists of indices denoting indices to be removed. The semantics are such that each sequence must be performed in order. I want to take these sequences and flatten them into one sequence of absolute indices to be removed.

This can be achieved by performing a series of sieves (somewhat akin to the Sieve of Eratosthenes). The caveat is that this technique is slow (quadratic).

Thus this group of relative indices:

``````R0: 0 3 10 15
R1: 2 7 20
R2: 1 11 12 14 17
R3: 0 1 2
``````

Would correspond to this group of absolute indices:

``````A0: 0 3 10 15
A1: 4 9 22
A2: 2 17 18 20 24
A3: 1 5 6
``````

And when merged into one sequence of absolute indices, I would have the following:

``````A': 0 1 2 3 4 5 6 9 10 15 17 18 20 22 24
``````

There may be any number of relative sequences, each of which may contain any number of elements and may have large gaps between indices. The input relative sequences are sorted in increasing order any may not contain duplicates.

Obtaining the intermediate `A#` lists is unnecessary. I only care about the list `A'` from the inputs `R#`.

Clarification on the algorithm

Let's take the list of non-negative integers

``````0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...
``````

And remove the indices given by R0

Then we have

``````1 2 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...
``````

The removed values yield A0 (`0 3 10 15`)

Now remove the indices given by R1

``````1 2 5 6 7 8 10 11 12 13 14 16 17 18 19 20 21 23 24 25 26 27 28 29 30 ...
``````

The removed values yield A1 (`4 9 22`)

Now remove the indices given by R2

``````1 5 6 7 8 10 11 12 13 14 16 19 21 23 25 26 27 28 29 30 ...
``````

The removed values yield A2 (`2 17 18 20 24`)

Now remove the indices given by R3

``````7 8 10 11 12 13 14 16 19 21 23 25 26 27 28 29 30 ...
``````

The removed values yield A3 (`1 5 6`)

• I don't get how you obtain the absolute values from the relative values, but once you have the values, you can merge them. If each input sequence is already sorted, this can be done in `O(n·m)` comparisons (n numbers in total, m input sequences), so it's effectively linear in complexity.
– amon
Commented Mar 6, 2014 at 16:05
• @amon: I have now described each step in detail. The slow part in the algorithm is obtaining the `A#`'s, not merging them into `A'` Commented Mar 6, 2014 at 16:24

Your complexity analysis is wrong. Generating each intermediate list is linear. Merging the lists if the final list has `n` elements and you have `k` intermediate lists is `O(k n)` with a naive algorithm, and `O(n log(k))` if you use a standard priority queue (which under the hood is probably a heap).