Modified counting sort algorithm?
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.