1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.