title: How does this c++ implementation of bead sort algorithm work?
body: <p>I have been trying to understand this code for hours unsuccessfully. I wrote my own version of bead sort algorithm however it is so slow.
  I want to understand why this one works so much more quickly.
  Here's info about the bead sort algorithm:<br>
  <a href="http://demonstrations.wolfram.com/ExtendedBeadSort/" rel="nofollow">http://demonstrations.wolfram.com/ExtendedBeadSort/</a><br>
  Can you please help me to understand how this algorithm works?</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  
  using std::cout;
  using std::vector;
  
  void distribute(int dist, vector&lt;int&gt; &amp;List) {
      //*beads* go down into different buckets using gravity (addition).
      if (dist &gt; List.size() )
          List.resize(dist); //resize if too big for current vector
  
      for (int i=0; i &lt; dist; i++)
          List[i]++;
  }
  
  vector&lt;int&gt; beadSort(int *myints, int n) {
      vector&lt;int&gt; list, list2, fifth (myints, myints + n);
      cout &lt;&lt; "sakums\n";
      cout &lt;&lt; myints&lt;&lt; "\n";
   //   for (vector&lt;int&gt;::iterator it = fifth.begin(); it != fifth.end(); ++it) cout &lt;&lt; " " &lt;&lt; *it &lt;&lt; "\n";
      cout &lt;&lt; "beigas\n";
  
      cout &lt;&lt; "#1 Beads falling down: ";
      for (int i=0; i &lt; fifth.size(); i++)
          distribute (fifth[i], list);
      cout &lt;&lt; '\n';
  
      cout &lt;&lt; "\nBeads on their sides: ";
      for (int i=0; i &lt; list.size(); i++)
          cout &lt;&lt; " " &lt;&lt; list[i];
      cout &lt;&lt; '\n';
  
      //second part
  
      cout &lt;&lt; "#2 Beads right side up: ";
      for (int i=0; i &lt; list.size(); i++)
          distribute (list[i], list2);
      cout &lt;&lt; '\n';
  
      return list2;
  }
  
  int main() {
      int myints[] = {734,3,1,24,324,324,32,432,42,3,4,1,1};
      vector&lt;int&gt; sorted = beadSort(myints, sizeof(myints)/sizeof(int));
      cout &lt;&lt; "Sorted list/array";
      for(unsigned int i=0; i&lt;sorted.size(); i++)
          cout &lt;&lt; sorted[i] &lt;&lt; ' ';
      system("PAUSE");
      return 0;
  }
  </code></pre>