title: What is this O(N*k) sorting algorithm?
body: <p>When working on "<a href="https://codegolf.stackexchange.com/a/4764/152">The fastest sort for BrainF***"</a>, I discovered this algorithm, which is O(N*k), where k is the maximum value in the input. It requires O(N) extra storage.</p>
  
  <p>The physical analogy is that you have N stacks of tokens. The height of the stack represents the value to be sorted. (Each token represents a bit). Set aside space for another N stacks. You take one token off the top of each stack that has tokens, and then add one to each stack in the new set from right to left until your hand is empty. Repeat until all original stacks are empty. Now the new set is sorted ascending left to right</p>
  
  <p>In C:</p>
  
  <pre><code> void sort(int A[], int N)
   {
      int *R = calloc(N,sizeof(int));
      do {
        int i,count=0; 
        for (i=0;i&lt;N;i++) if A[i] { count++; A[i]--;}
        for (i=0;i&lt;count;i++) R[i]++;
      } while (count);
      memcpy(A,R,N);  //A is now sorted descending.
      free(R);
   }
  </code></pre>
  
  <p>Does this algorithm have a name?  It seems similar to a <a href="http://en.wikipedia.org/wiki/Bead_sort" rel="nofollow noreferrer">Bead Sort</a>, but I don't think it's quite the same.</p>