Why do we need cumulative sum in Radix Sort?

Question

we calculate each digit of the number, after which we count the cumulative sum, why is it necessary?

# count of each digit in arr
    for i in range(len(arr)):
        index = (arr[i] // place) % 10
        count[index] += 1

# calculate cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

Answer 1

This is done to set the ending indexes of the destination array's logical bins during a radix sort pass.

Say there are 7 zeroes, 5 ones, 3 twos, 4 threes, ..., then the result is:

Using the questions code:

count[] = {7,  5,  3,  4 ... }      # after first  loop
count[] = {7, 12, 15, 19 ... }      # after second loop

During a radix sort pass, the array is scanned and stored backwards.

    for i in range(len(arr)-1, -1, -1):
        index = (arr[i] // place) % 10
        count[index] = count[index] - 1
        dest[count[index]] = arr[i]

This can be changed to set starting indexes and scanning the array in forwards order:

# count of each digit in arr  (same as first loop in question's code)
    for i in range(len(arr)):
        index = (arr[i] // place) % 10
        count[index] = count[index] + 1

# calculate cumulative count
    j = 0
    for i in range(0, 10):
        k = count[i]
        count[i]  = j
        j = j + k

Then the result is:

count[] = {7,  5,  3,  4 ... }       # after first  loop
count[] = {0, 7, 12, 15, 19, ... }   # after second loop

During a radix sort pass, the array is scanned and stored forwards

    for i in range(0, len(arr)):
        index = (arr[i] // place) % 10
        dest[count[index]] = arr[i]
        count[index] = count[index] + 1

Example 4 pass base 256 radix sort for positive 32 bit integers.

def sort(a):                            # 4 pass radix sort base 256
    b = [0] * len(a)                    # allocate b
    for l in range(0, 32, 8):           # l = shift count
        cnt = [0] * 256                 # allocate, zero cnt
        for i in range(len(a)):         # generate counts
            idx  = (a[i] >> l) % 256
            cnt[idx] = cnt[idx] + 1
        j  =  0                         # convert to indexes
        for i in range(0, 256):
            k = cnt[i]
            cnt[i] = j
            j = j + k
        for i in range(0, len(a)):      # radix sort pass
            idx = (a[i] >> l) % 256
            b[cnt[idx]] = a[i]
            cnt[idx] = cnt[idx] + 1
        a,b = b,a                       # swap a,b