title: Radix sorting a vector of ints using a vector of int vectors
body: <p>I recently tried implementing radix sort for a vector of pair of integers (where the second element is considered only when the first elements are equal). I did so by applying counting sort twice - first to the second element of the pair, and then to the first element. Here is how I implemented the counting sort at first:</p>
  
  <pre><code>//vector to be sorted (of size n).
  vector&lt;int&gt; arr;
  
  //arr gets filled here
  
  
  //N-1 is the maximum number which can occur in the array. N was equal to n in my case
  vector&lt;vector&lt;int&gt; &gt; mat(N);
  
  for (int i=0;i&lt;n;i++)
  {
      mat[arr[i]].push_back(i);
  }
  
  //array in which the sorted array will be stored
  vector&lt;int&gt; arr2;
  
  for (int i=0;i&lt;N;i++)
  {
      for(int j=0;j&lt;sz(mat[i]);j++) arr2.push_back(arr1[mat[i][j]]);
  }
  </code></pre>
  
  <p>The first for loop obviously runs in O(n). Since the 'mat' array has exactly n entries, it will be accessed at most 2n times in the second (nested) loop. This implies that the above code has a time complexity of O(n), as it should have.</p>
  
  <p>I then compared the running time of this code with the STL sort() (which has a time complexity of  O(nlog(n))) by running both of them on an array of 10^6 elements. To my great surprise, the STL sort() ended up performing slightly better than my implementation of radix sort.</p>
  
  <p>I then changed my counting sort implementation to the following:</p>
  
  <pre><code>//vector to be sorted (of size n).
  vector&lt;int&gt; arr;
  
  //arr gets filled here
  
  //N-1 is the maximum number which can occur in the array. N was equal to n in my case
  vector&lt;int&gt; temp(N,0);
  
  for(int i=0;i&lt;n;i++) temp[arr[i]]++;
  
  for(int i=1;i&lt;N;i++) temp[i]+=temp[i-1];
  
  //array in which the sorted array will be stored
  vector&lt;int&gt; arr2(n);
  
  for(int i=n-1;i&gt;=0;i--) arr2[--temp[arr[i]]]=arr[i];
  </code></pre>
  
  <p>This time, the radix sort did run about 5-6 times faster than the STL sort(). This observation has left me wondering why is it that the my first radix sort implementation runs so much slower than the second one, when both of them are O(n)?</p>