title: How does Radix Sort work?
body: <p>I don't know why this is so hard for me to wrap my head around.  I've looked through the wiki pages, and pseudo code (as well as actual code) trying to understand how radix sort algorithms work (with respect to buckets).</p>
  
  <p>Am I looking into the wrong thing here?  Should I be looking into bucket sort maybe?  Can someone give me a dumbed down version of how it works?  For reference, here is a codeblock that <em>supposedly</em> performs a radix sort:</p>
  
  <pre><code>// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
  // For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
  void radixSort(int* input, int size, int digit)
  {
      if (size == 0)
          return;
  
      int[10] buckets;    // assuming decimal numbers
  
      // Sort the array in place while keeping track of bucket starting indices.
      // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
      // then let bucket[i+1] = bucket[i]
  
      for (int i = 0; i &lt; 10; ++i)
      {
          radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
      }
  }
  </code></pre>
  
  <p>And I've looked at non-recursive solutions also:</p>
  
  <pre><code>void radixsort(int *a, int arraySize)
  {
      int i, bucket[sortsize], maxVal = 0, digitPosition =1 ;
      for(i = 0; i &lt; arraySize; i++) {
          if(a[i] &gt; maxVal) maxVal = a[i];
      }
  
      int pass = 1; 
      while(maxVal/digitPosition &gt; 0) {
          // reset counter 
          int digitCount[10] = {0};
  
          // count pos-th digits (keys) 
          for(i = 0; i &lt; arraySize; i++)
              digitCount[a[i]/digitPosition%10]++;
  
          // accumulated count 
          for(i = 1; i &lt; 10; i++)
              digitCount[i] += digitCount[i-1];
  
          // To keep the order, start from back side
          for(i = arraySize - 1; i &gt;= 0; i--)
              bucket[--digitCount[a[i]/digitPosition%10]] = a[i];
  
          for(i = 0; i &lt; arraySize; i++)
              a[i] = bucket[i];
  
          cout &lt;&lt; "pass #" &lt;&lt; pass++ &lt;&lt; ": ";
          digitPosition *= 10;
      } 
  
  }
  </code></pre>
  
  <p>Specifically, this line is giving me troubles.  I've tried walking through it with pen and paper, but I still can't figure out what this is doing:</p>
  
  <pre><code>   // To keep the order, start from back side
          for(i = arraySize - 1; i &gt;= 0; i--)
              bucket[--digitCount[a[i]/digitPosition%10]] = a[i];
  </code></pre>