# Sort already sorted array - after changing several elements

Problem:

Given $S$ — a sorted array where some of the elements were randomly changed, assuming that you're provided with an $S_1$ — an array of indexes of changed elements. Design an algorithm that will sort the array in $O(n)$ time.

Additionally, we know that $\text{length of }S_1\le\log_2(\text{length of }S)$.

Example:

$S$ — [3, 5, 7, (20), 15 ,(0) ,16]

$S_1$ — [3, 5]

() - Changed elements

Question:

I have some troubles designing the algorithm. My first idea was to just use Count or Radix sort algorithm, but as the values which are changed can be random I've ruled out count sort as potential candidate.

The second idea is to:

1. Load the values based on indexes of $S_1$ into new array $S_x$.

2. Rewrite $S$ without the elements of indexes provided in $S_1$.

3. Sort $S_x$.

4. Use "Merge" procedure from Merge Sort on $S_x$ and $S$.

However that still will leave me with $O(n\log n)$ as I'll need to sort $S_x$ array. I'll appreciate any advice on the approach.

• Sorting the array $S_x$ takes $O(m\log m)$, where $m = |S_1|$. Since $m \leq \log n$, sorting $S_x$ takes time $O(\log n\log\log n)$. So this strategy actually works under the much weaker assumption $|S_1| = O(|S|/\log |S|)$. – Yuval Filmus Apr 27 '18 at 15:21

Note the length of $S_1$ is no more than $\log_2n$, so the time you need to sort $S_x$ is $O(\log n\log\log n)$, which is $O(n)$.