# 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]>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 lets 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\}$?

• @kocko one randomly chosen element $j$ with $A[j]>0$ is decreased with $x \in \{1 \dots A[j]\}$ – user8 Nov 24 '15 at 14:03
• (If a comment seeks clarification, augment the question instead of commenting the comment.) I am confused about $j$ being an element, as well as an index into $A$ and $C$. What is $k$? If the number of counts (length of $C$) or $j$ was $O(k)$ and $j$ was known, where is the problem? – greybeard Nov 24 '15 at 16:38

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 <- count of the elements with value i (i >= 0) 0 0 0 0 0 <- flag if the i-th element has been reduced. ` When you reduce an element with value$j$, you will do: 1.$C[0][j]$--; // decrease the count of$j$2.$C[0][j - x]++$; // increase the count of$(j - x)$3.$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. • Given an array A, almost sorted with CountingSort, and an index$j$where an element of A was reduced, how do you get A sorted in$O(k)$time? – greybeard Nov 24 '15 at 15:00 • I don't. The question is "How can I now sort the modified array in O(k)?" – Konstantin Yovkov Nov 24 '15 at 15:03 • Given an array$A$, almost sorted with CountingSort, with the only exception that element of$A$at a known index$j$was reduced, how do you get$A$sorted in$O(k)$time, even with the counts still around? As in: what operations on$A$take constant time, and how is their count bounded in growth by$O(k)$with increasing$n$- whatever$k$may be? Or: How does knowing the modification index make this an$O(k)$task? – greybeard Nov 24 '15 at 15:08 • See my answer for an improvement. – Yuval Filmus Dec 27 '15 at 0:15 Here is an example. Suppose that the sorted array looks like this: $$0000111222233444.$$ Now we reduce one of the$3$entries to$1$. The new sorted array is $$0000111122223444.$$ Let's put them side by side: $$0000111222233444 \\ 0000111\mathbf{1}222\mathbf{2}3444$$ The number of changes is bounded by the number of distinct elements (presumably, your$k$). Moreover, you can find the indices of the changes using your array$C$. This allows you to update the sorted array in time$O(k)\$. I'm leaving the details to you.