title: Counting sort : Why we need sum of previous counts?
body: <p>I was reading about counting sort and one of the steps of algorithm is </p>
  
  <p><a href="https://i.stack.imgur.com/Yy2Tw.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Yy2Tw.png" alt="Counting sort"></a></p>
  
  <pre><code>for(i = 1 to k) 
     c[i] = c[i]+c[i-1];
  </code></pre>
  
  <p>Why do we need this step?</p>
  
  <p>Why can't we use this instead</p>
  
  <pre><code>for(i = 0 to k)
      while(c[i]--)
          Output i/Use i as key.
  </code></pre>
  
  <p>One problem I thought of was if we wanted data itself (probably like a string which referred to particular index).</p>
  
  <p>But then , we could use a 2d Vector. 
  What is bad in this approach where we sort data from 0 to 99.</p>
  
  <pre><code>int a[100];
  for(int i = 0 ; i &lt; 100; ++i)
      a[i] = 0;
  string s;
  vector&lt;vector&lt;string&gt;&gt; data(100);
  int temp;
  for(int i = 0 ; i &lt; n ; ++i){
      cin&gt;&gt;temp;
      a[temp]++;
      getline(cin,s);
      data[temp].push_back(s);
  }
  
  for(int i = 0 ; i &lt; 100; ++i){
      int current = 0;
      while(a[i]--){
          cout&lt;&lt;data[i][current]&lt;&lt;" ";
          ++current;
      }
  }
  </code></pre>