title: Optimize LSD radix sort in python
body: <p>I'm trying to implement LSD radix sort in python, but my code used 4 loop, is there any way I can do it in three or less?</p>
  
  <p><br></p>
  
  <p>Here is the 4 loops:</p>
  
  <p>First loop iterate through the input list, convert it to desired radix, and change each number to a reversed list, like so:</p>
  
  <pre><code>123 --&gt; [3,2,1]
  </code></pre>
  
  <p>Second loop iterate through the newly created list, make them have the same length by adding 0, add a pointer to the corresponding element in input list, then reverse the list.Like this:</p>
  
  <pre><code>input: [1234, 56, 7]
  After first loop: [[4, 3, 2, 1], [6, 5], [7]]
  After the second loop: [[0, 1, 2, 3, 4], [1, 0, 0, 5, 6], [2, 0, 0, 0, 7]]
  </code></pre>
  
  <p>Third loop sort element in LSD order using counting sort, code is below.</p>
  
  <p>Fourth loop put every thing in a new list with sorted order using the pointers.
  <br></p>
  
  <p>Here's the code for radix sort:</p>
  
  <pre><code>def radix_sort(collection, radix):
  
      new_collect = []
      max_len = 0
  
      #loop through collection, convert them to desired form and put in new_collect
      for i in collection:
          num = []
          while i &gt;= radix:
              remain = i % radix
              num.append(remain)
              i = i // radix
          num.append(i)
          new_collect.append(num)
  
          if len(num) &gt; max_len:
              max_len = len(num)
  
      #loop through new_collect, extend the each item to same length
      for i in range(0, len(new_collect)):
          space = max_len - len(new_collect[i])
          patch = [0 for j in range(space)]
          new_collect[i].extend(patch)
  
          #add a pointer to the corresponding element in collection
          new_collect[i].append(i)
          new_collect[i].reverse()
  
      #sort by digit with counting_sort
      for i in range(-1, -1 - max_len, -1):
          new_collect = counting_sort(new_collect, radix - 1, i)
  
      #create a new list with same length as collection
      return_list = list(range(len(collection)))
  
      #put elements in collection to return_list, using the pointer in new_collect
      for i in range(0, len(collection)):
          return_list[i] = collection[new_collect[i][0]]
  
      return return_list
  </code></pre>
  
  <p>And here is the code for counting sort:</p>
  
  <pre><code>def counting_sort(collection, d_range, digit = -1):
  
      d_range += 1
  
      B = list(range(len(collection) + 1))
      C = list(range(d_range))
  
      for i in range(d_range):
          C[i] = 0
  
      for j in collection:
          #C[j] = |{key = j}|
          C[j[digit]] += 1
  
      for i in range(1, d_range):
          #C[i] = |{key &lt;= i}|
          C[i] = C[i] + C[i - 1]
  
      for i in range(len(collection) - 1, -1, -1):
          B[C[collection[i][digit]]] = collection[i]
          C[collection[i][digit]] -= 1
  
          return B[1:]
  </code></pre>