title: Radix sort digit compares
body: <p>I have an implementation of LSD Radix Sort algorithm and was wondering how to count the number of digit comparisons during the sort procedure? I know that the algorithm is not comparison based but there is still some kind of a comparison between digits of the Integer elements the algorithm sorts. Can someone point out where the comparison is taking place?</p>
  
  <p>Thanks!</p>
  
  <p>LSDRadixSort:</p>
  
  <pre><code>public static void lsdRadixSort(int[] a)
  {
      final int BITS = 32; // each int is 32 bits 
      final int R = 1 &lt;&lt; BITS_PER_BYTE; // each bytes is between 0 and 255
      final int MASK = R - 1; // 0xFF
      final int w = BITS / BITS_PER_BYTE;  // each int is 4 bytes
  
      int n = a.length;
      int[] aux = new int[n];
  
      for(int d = 0; d &lt; w; d++)
      {
          // compute frequency counts
          int[] count = new int[R+1];
  
          for(int i = 0; i &lt; n; i++)
          {           
              int c = (a[i] &gt;&gt; BITS_PER_BYTE*d) &amp; MASK;
              count[c + 1]++;
          }
  
          // compute cumulates
          for(int r = 0; r &lt; R; r++)
          {
              count[r+1] += count[r];
          }
  
          //for most significant byte, 0x80-0xFF comes before 0x00-0x7F
          if(d == (w - 1))
          {
              int shift1 = count[R] - count[R/2];
              int shift2 = count[R/2];
  
              for(int r = 0; r &lt; R/2; r++)
              {
                  count[r] += shift1;
              }
  
              for(int r = (R/2); r &lt; R; r++)
              {
                  count[r] -= shift2;
              }
          }
  
          // move data
          for(int i = 0; i &lt; n; i++)
          {
              int c = (a[i] &gt;&gt; BITS_PER_BYTE*d) &amp; MASK;
              aux[count[c]++] = a[i];
          }
  
          // copy back
          for(int i = 0; i &lt; n; i++)
          {
              a[i] = aux[i];
          }
      }
  }
  </code></pre>