Modified counting sort algorithm? So I have an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A[j]&gt;0$ by $x \in \{1 \dots A[j]\}$. I still have the counting array $C$, since I have sorted the array with counting sort. 

The question is: how can I now sort the modified array in $O(k)$?

So far: Obviously I won't need to check all the elements of $A$ again, otherwise it would be $O(n)$. I have to modify the $C$ array somehow. If you subtract $C[j+1] - C[j]$ you have the number of elements in the respective  interval (like $0 - 0=0$ are 0 Elements of value 0, $1-0 = 1$ is 1 Element of value 1). But this is still only for the old array. 

How can I understand which element from $A$ is reduced only by looking at $C$?

Example: 

Sorted $A[4] = \{1,3,4,4\}$, reduce let`s say $j = 2$ with $A[2] = 4$ by $x \in \{1, \dots , 4\}$. Let $x = 4$ then we have $A[4] = \{1,3,0,4\}$. How can I sort it now in $O(k)$ like $A[4] = \{0,1,3,4\}$?
How can I understand which element from A is reduced only by looking at C?


I guess you can make $C$ array two-dimensional $C[2][n]$ and in the second array you will initially (and after the counting step) store 0-es only. (This means when counting you will fill only the $C[0][n])

After, the counting step, your $C$ array should look like (taking the example above):

0 1 0 0 2  &lt;- count of the elements with value i (i &gt;= 0)
0 0 0 0 0  &lt;- flag if the i-th element has been reduced.


When you reduce an element with value $j$, you will do:


$C[0][j]$--; // decrease the count of $j$
$C[0][j - x]++$; // increase the count of $(j - x)$ 
$C[1][j]$ = 1; // set $j$ as decreased


This way, when you want to check if a value $j$ was reduced, you can just get the value of $C[1][j]$ and check if it is $1$. The complexity of this will be $O(1)$.


  How can I sort it now in $O(k)$?


For the further sorting of the array, I don't think it's possible to do it in linear time (as Quicksort's complexity is $O(nlogn)$). You can, however, shift the decreased element to the left or to the right.