# Sorts a sequence of positive integers using the radix sort algorithm.
from collections import deque

def radixSort( intList, numDigits ):
  """Radixsort"""
  # Create an array of queues to represent the bins.
  binArray = list()
  for k in range( 10 ):
    binArray.append( deque() )
    
   # The value of the current column.
  column = 1                   
  
   # Iterate over the number of digits in the largest value.
  for d in range( numDigits ):
    
     # Distribute the keys across the 10 bins.
    for key in intList :                
      digit = (key // column) % 10
      binArray[digit].append( key )
      
     # Gather the keys from the bins and place them back in intList.
    i = 0                          
    for bin in binArray :
      while len(bin) != 0:
        intList[i] = bin.popleft()
        i += 1                     
      
     # Advance to the next column value.
    column *= 10              

def radixSortR( intList, numDigits ):
  """Radix sort in reverse order (large to small)"""
   # Create an array of queues to represent the bins.
  binArray = list()
  for k in range( 10 ):
    binArray.append( deque() )
    
   # The value of the current column.
  column = 1                   
  
   # Iterate over the number of digits in the largest value.
  for d in range( numDigits ):
    
    # Distribute the keys across the 10 bins.
    for key in intList :                
      digit = (key // column) % 10
      binArray[digit].append( key )
      
    # Gather the keys from the bins and place them back in intList.
    l = len( binArray )
    c = 0
    for i in range ( l ):
      j = l - i - 1
      while len( binArray[ j ] ) != 0:
        intList[ c ] = binArray[ j ].popleft()
        c += 1                     
      
     # Advance to the next column value.
    column *= 10