Counting sort in O(1) space

I have the following counting sort, but the space complexity is too high for me, I'm looking for a way to do it in space complexity of O(1)

MyCountingSort(A, B, k)
    for i = 0 to k
       do G[i] = 0
    for j = 0 to length[A]
        do G[A[j]] = G[A[j]] + 1
    for i = 1 to k
       do G[i] = G[i] + G[i-1]
    for j = length(A) to 1
       do B[G[A[j]]] = A[j]
       G[A[j]] = G[A[j]] - 1 

Currently, the algorithm is allocating O(k) space. Assuming k<=A.length, how I can improve the algorithm space complexity to O(1)?

I'm assuming here that A is your input array, B is your output array. Thus, |A| = |B|. I'm further assuming that k is the maximum number of values we might encounter (for instance, if A contains only positive numbers from 1 to k or from 0 to k-1). It would help us if you specify this kind of details when asking a question, but I'm guessing that this is more or less what you are asking. :)

Since we have the very convenient additional constraint that k <= |A|, we can use our given arrays A and B as intermediate storage for our index array. Essentially, make B your G in your code and perform the 1st and 2nd loop on it. Then we make the cumulative additions (3rd loop).

Once we have finished this, we can copy B back to A. Finally, we overwrite B with our final sorted array (4th loop in your code).

This way, no memory is allocated apart from the input parameters already given. In general, the space complexity of an algorithm is defined as independent of the input of the algorithm. Since we are only recycling the input arrays and not allocating anything ourselves, this algorithm is indeed of O(1) space complexity.

Notice that in the general case (where k is not necessarily <= |A|), it will not be this easy. In addition, it is only because the output array B has already been provided to us as an input that we can make use of this "trick" of using it for our internal use and thus not have to allocate any new memory.