Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$?
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)$.
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.
