Sorting a sorted array after increasing several elements

Question

I know that most of the efficient sort algorithms can run with a complexity of $O(n\cdot log(n)),ドル but this is given an unsorted array.

However, given that the initial array is already sorted, is there an algorithm that can sort the array after multiplying several elements by 2 (or increasing them by some value) with complexity of $O(n)$?

Answer 1

You can update the array using the merge procedure of mergesort. Decompose your array into two smaller arrays: unchanged elements and updated elements. Since multiplying elements by 2ドル$ preserves their relative order, you can do this decomposition in $O(n)$ while producing two sorted smaller arrays. You can then merge them in $O(n)$.

Answer 2

An alternative (to special handling of changed values, which, after all, might still be in the right place) might be smoothsort, designed to run $O(n)$ on sorted arrays and "degenerate" to $O(n \cdot log(n))$ with increasing disorder, well, smoothly.

Answer 3

Yuvals method works very well if you know which elements have been modified. If you don’t know which were modified, you make one pass through the array looking for elements followed by a smaller one. One of two must have been modified, so you move them both into a separate array. If there are k elements modified you move at most 2k elements. Apart from that you use Yuvals algorithm.