Radix Without Stability
This counting sort produces a correctly ordered output, but it walks the input forwards:
def counting_sort(A, key, u):
C = [0] * u
for x in A: C[key(x)] += 1
for v in range(1, u): C[v] += C[v-1] # C[v] = count of keys <= v
B = [None] * len(A)
for x in A: # forwards
C[key(x)] -= 1
B[C[key(x)]] = x
return B
It is used as the per-digit pass of a two-pass LSD radix sort on [21, 11, 12, 22]: first by the ones digit, then by the tens digit. What comes out?
Sign in to answer questions and track your progress
Sign In