@evinda Write the array elements in base $4$, that gives $33,\, 13,\, 32,\, 01$. Count the numbers with last digit $k$, that gives 0->0, 1->1, 2->1, 3->2
. Now take the cumulative sum of the count
array: 0->0, 1->1, 2->2, 3->4
. Now we fill array B
, walking backwards from the end of array A
. Last element is $01$ with last digit $1$.
We look up $1$ in the count
array and find there is one number whose last digit is $\leqslant 1$, so that is placed at position $1-1 = 0$ in array B
. And we decrease count[1]
so after that, count
looks 0->0, 1->0, 2->2, 3->4
, and B
looks 01,-,-,-
. We move forward to the penultimate element of A
, which is 32
(in base $4$).
Last digit is $2$, so we look up $2$ in count
, the value is $2$, hence the element is placed at position $2-1 = 1$ in array B
. We decrease count[2]
, and get 0->0, 1->0, 2->1, 3->4
in count
, and 01,32,-,-
in B
. We move to the next element of A
, which is $13$ ($= 7$), with last digit $3$.
We look up $3$ in count
, that gives us $4$, and hence the element is placed at index $4-1=3$ in B
. Also, count[3]
is decremented. Now, count
is 0->0, 1->0, 2->1, 3->3
, and B
is 01,32,-,13
. We move the the first element of A
, $33_4$. We look up the last digit: count[3] = 3
. So that element is placed in B[3-1]
, and decrement count[3]
. Final looks: count
is 0->0, 1->0, 2->1, 3->2
and B
is 01,32,33,13
.