Radix Sort Speed

Question

I have implemented a radix sort algorithm in Python 3. It first finds the maximum number of digits in the list, then changes them to strings and adds 0's. For example, [7, 23, 107, 1, 53] to ['007', '023', '107', '001', '053']. I then make a new matrix, [[] * 10]. I append the numbers with last digit of 0 in lst[0], numbers with last digit of 1 in lst[1], etc. I then flatten the matrix into a list, and recurse with the lst, and with the position one less than the one before (in this case, the second to last digit). Can I get advice on how to improve it? Here is my code:

def radix_sort(lst):
    '''list -> list'''

    #finds maximum number of digits in list
    num_of_digits = max([len(str(x)) for x in lst])

    #Adds 0s to the front of the number if necessary and changes it to a string
    for x in range(len(lst)):
        lst[x] = '0' * (num_of_digits - len(str(lst[x]))) + str(lst[x])

    #helper function to sort based on the position
    def helper(lst, pos):
        '''list, int -> list'''
        #places numbers with 0 in the position in the ans[0], 1 in the position in ans[1], etc.
        ans = [[] for _ in range(10)]
        
        #adding numbers to the position in ans
        for x in lst:
            ans[int(x[pos])].append(x)
        
        #flattened list, reusing lst to save memory
        lst = []
        for x in ans:
            for y in x:
                lst.append(y)
        
        #we have sorted the whole list
        if pos == 0:
            return lst
        
        #recurse again with smaller position
        return helper(lst, pos - 1)

    #changing the strings to integers and returning
    return [int(x) for x in helper(lst, num_of_digits - 1)]

Answer 1

        #flattened list, reusing lst to save memory
        lst = []

That doesn't save memory. The caller of the current helper call still has a reference to the "old" list, so it'll remain in memory in addition to this new one. You'll have one list per call level. To actually save memory, you could do lst.clear() instead, so that all levels use the same single list.

To further save memory, do del ans, x, y after you rebuilt lst from them before you call helper recursively, otherwise they'll remain in memory as well, again once per call level.

For example for lst = ['1' * 800] * 1000, these improvements changed the peak memory usage from over 15 MB to less than 0.5 MB in this test of mine:

import tracemalloc

lst = ['1' * 800] * 1000
tracemalloc.start()
radix_sort(lst)
peak = tracemalloc.get_traced_memory()[1]
print(peak)

Or just do it iteratively instead of recursively, then you likely wouldn't have these issues in the first place and you wouldn't have to worry about recursion limit errors due to large numbers.

Here's an iterative one with a few other changes:

def radix_sorted(lst):
    '''list -> list'''
    lst = list(map(str, lst))
    width = max(map(len, lst))
    lst = [s.rjust(width, '0') for s in lst]
    for i in range(width)[::-1]:
        buckets = [[] for _ in range(10)]
        for s in lst:
            buckets[int(s[i])].append(s)
        lst = [s for b in buckets for s in b]
    return list(map(int, lst))

Answer 2

It isn't necessary to convert the numbers to strings and zero-pad them.

BASE = 10

def radix_sort(lst, base=BASE):
    biggest_number = max(lst)
    place = 1

    while place <= biggest_number:
        buckets = [[] for _ in range(BASE)]
        for number in lst:
            index = number // place % BASE
            buckets[index].append(number)

        lst = []
        for bucket in buckets
            lst.extend(bucket)

        place *= BASE

    return lst