Sort already sorted array - after changing several elements

Question

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.

Answer 1

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)$.

Answer 2

If you are given the indices, it is trivial. Sort the indices. Remove the changed elements into a separate array and pack the first one together. Sort the changes elements and merge with the first array. All in O(n) as long as the number of changed elements is O(n / log n).

Much more difficult if you don’t know which elements are changed.