Implement LSD radix sort in python
1. Introduction

In this answer I'm just going to look at the function counting_sort. You'll see that there's plenty here for one answer.

2. Review


There's no docstring. What does this function do? What arguments does it take? What does it return?
When a function returns a result, it's conventional to name it with a noun or noun phrase describing the result. Hence the built-in function is called sorted rather than sort.
The first argument is named collection but this needs to be a sequence, so a name like seq would be better.
If the second argument were the number of keys (rather than the maximum key) then there would be no need to increment it (and similarly no need to decrement this argument in the callers).
The variables B and C could have more descriptive names, for example result and count respectively.


3. Performance


The lists B and C can be initialized more quickly using the * operator:

B = [None] * (len(collection) + 1)
C = [0] * d_range

The main loop looks like this:

for i in range(len(collection) - 1, -1, -1):
    B[C[collection[i][digit]]] = collection[i]
    C[collection[i][digit]] -= 1


But this means that collection[i] has to be looked up three times on each iteration. It is faster to iterate over the items in the collection (using reversed to do so in reverse order), avoiding the lookups:

for item in reversed(collection):
    B[C[item[digit]]] = item
    C[item[digit]] -= 1

Now, item[digit] has to be looked up twice on each iteration. It is faster to cache this in a local variable:

for item in reversed(collection):
    k = item[digit] # the key for this item
    B[C[k]] = item
    C[k] -= 1

Now, item[digit] is looked up twice for each item, once when counting the number of occurrences of each key, and once in the main loop. This can be reduced to a single lookup by creating an array of keys at the start:

keys = [item[digit] for item in collection]


and then using this when counting keys and in the main loop.
If C[k] is changed so that it has the value \$\left|\{\mathrm{key}&lt;k\}\right|\$ rather than \$\left|\{\mathrm{key}≤k\}\right|\$, then this has three benefits: (i) the main loop can iterate over the collection in forward order, avoiding the call to reversed; (ii) the slice B[1:] at the end is avoided; (iii) the initialization of B is simplified.


Applying all these changes results in the following code:

def counting_sorted(seq, nkeys, digit=-1):
    """Return a new list containing all the items from seq in ascending
    order of item[digit], which must be a non-negative integer less
    than the parameter nkeys.

    """
    keys = [item[digit] for item in seq]

    # count[k] = |{key = k}|
    count = [0] * nkeys
    for k in keys:
        count[k] += 1

    # index[k] = |{key &lt; k}|
    index = [0] * nkeys
    for k in range(nkeys - 1):
        index[k + 1] = index[k] + count[k]

    result = [None] * len(seq)
    for k, item in zip(keys, seq):
        result[index[k]] = item
        index[k] += 1
    return result


I find that this reduces the runtime to about 60% of the original. On my test data this is a little faster than the built-in sorted.

4. Interface improvements

There are a couple of infelicities in the interface to counting_sorted, and I think that for ease of use and understandability of the code it would be worth fixing them, even at the expense of a few percent slowdown.


The function requires us to pass in the value of nkeys. This is fragile (it would be easy to pass in the wrong value) and redundant (it can be computed from the data). So I would remove this parameter and add the line:

nkeys = max(keys) + 1


after the computation of keys.
The function looks up the sort key for each item by indexing the item with digit. But this only works for some kinds of item. Other sorting functions (like the built-in sorted) take a general key-derivation function, and I think it would be better to do so here. In your radix sort function you can make the key functions you need using operator.itemgetter


Revised code:

def counting_sorted(seq, key=None):
    """Return a new list containing all the items from seq in ascending
    order. A custom key function can be supplied to customise the sort
    order. Sort keys must be non-negative integers.

    """
    if key is None:
        keys = seq
    else:
        keys = list(map(key, seq))
    nkeys = max(keys) + 1

    # count[k] = |{key = k}|
    count = [0] * nkeys
    for k in keys:
        count[k] += 1

    # index[k] = |{key &lt; k}|
    index = [0] * nkeys
    for k in range(nkeys - 1):
        index[k + 1] = index[k] + count[k]

    result = [None] * len(seq)
    for k, item in zip(keys, seq):
        result[index[k]] = item
        index[k] += 1
    return result


5. Answers to questions


Naming is one of the hardest things about programming. Reading other peoples' code is good practice—you'll find yourself continually thinking, "what on earth did the programmer mean by foo?" and then you can apply the same thought process to your own code.
I wanted to avoid the slice on B, and this change followed straightforwardly.
I think you're right and nkeys was a poor choice of name. What I meant by this was "number of (possible) distinct key values" but the name nkeys doesn't make that clear. (Naming is hard!)
You're right in this particular case that passing radix would be faster than calling max. But you'll see in the introduction to §4 that I gave my reasons for making these changes as "ease of use and understandability". The point is that by generalizing the function (so that it works in the general case, and not just in one specific context) it is easier to re-use, and easier for other programmers to understand and maintain.

This is a theoretical concern—after all, maybe you'll never want to re-use this code and no other programmers will ever work on it. But considered as an exercise I think it's valuable: in a professional context it's a good idea to make code as clear and easy to maintain as possible.
It's easy to change radix_sort to use the revised interface. There are two sensible approaches. (i) Transform each item into a list as before, and then pass key=itemgetter(-1) on the first iteration, key=itemgetter(-2) on the second iteration, and so on. (ii) Leave the items unchanged, and pass key=lambda x: x % radix on the first iteration, key=lambda x: (x // radix) % radix on the second iteration, and so on.
I use timeit.
As I said in the introduction, this answer is quite long enough already. Maybe someone else can have a look at radix_sort?