title: Error implementing Radix sort in C++
body: <p>I’m trying to implement Radix-Sort with arrays of long int. </p>
  
  <p>My Algorithm has 2 inputs:</p>
  
  <ul>
  <li>The number ’n’ of elements to be sorted</li>
  <li>The number ‘b’ of bits per digit (So, insted of taking the last decimal number, I take the groups of ‘b’ digits, representing one digit)</li>
  </ul>
  
  <p>But, when I try to sort the vector, I find 2 problems:</p>
  
  <ul>
  <li>First one: It doesn’t sort the vector properly</li>
  <li>Second one: I have implemented it for taking from the last group of bits to the first one. But it seems like it tries to sort in in the opposite direction.</li>
  </ul>
  
  <p>Here is the code:</p>
  
  <pre><code>#define MAX_BITS sizeof(long int)*8
  #define VectorL vector&lt;long int&gt;
  
  struct Compare
  {
     int beg = 0;
     int bits_per_digit = 2;
  
     Compare(int x, int y){
         beg = x;
         bits_per_digit = y;
     }
  
     bool operator() (long&amp; a, long&amp; b){
         int _begin = beg;
         int _final = _begin + bits_per_digit - 1;
  
         assert(_begin &lt;= _final); // b==f if  bits_per_digit = 1;
  
         bitset&lt;sizeof(long int)&gt; _x(a), _y(b);
  
         for(_begin; _begin &lt;= _final; _begin++)
             if(_x[_begin] != _y[_begin])
                 return (_x[_begin] &lt; _y[_begin]) ? true : false;
  
         return false;
     }
  };
  
  void ALG(VectorL&amp; nums, int n, int b)
  {
     assert(nums.size() == n);
     assert(MAX_BITS%b == 0);
  
     int _grupos = MAX_BITS/b;
     Compare myobject(MAX_BITS,b);
  
     for (int g = 1; g &lt;= _grupos; g++)
     {
         myobject.beg -= b;
  
         sort(nums.begin(), nums.end(), myobject);
     }
  }
  </code></pre>
  
  <p>Here’s the main:</p>
  
  <pre><code>int n=5, b=2;
  VectorL nums(n);
  nums[0] = 2;
  nums[1] = 6;
  nums[2] = 1;
  nums[3] = 5;
  nums[4] = 0;
  
  ALG(nums, n, b);
  </code></pre>
  
  <p>And here’s the output:</p>
  
  <pre><code>Initial Vector: 2 6 1 5 0
  From bit 62 to bit 63
  Vector after the 1º sort: 2 6 1 5 0
  From bit 60 to bit 61
  Vector after the 2º sort: 2 6 1 5 0
  From bit 58 to bit 59
  Vector after the 3º sort: 2 6 1 5 0
  From bit 56 to bit 57
  Vector after the 4º sort: 2 6 1 5 0
  From bit 54 to bit 55
  Vector after the 5º sort: 2 6 1 5 0
  From bit 52 to bit 53
  Vector after the 6º sort: 2 6 1 5 0
  From bit 50 to bit 51
  Vector after the 7º sort: 2 6 1 5 0
  From bit 48 to bit 49
  Vector after the 8º sort: 2 6 1 5 0
  From bit 46 to bit 47
  Vector after the 9º sort: 2 6 1 5 0
  From bit 44 to bit 45
  Vector after the 10º sort: 2 6 1 5 0
  From bit 42 to bit 43
  Vector after the 11º sort: 2 6 1 5 0
  From bit 40 to bit 41
  Vector after the 12º sort: 2 6 1 5 0
  From bit 38 to bit 39
  Vector after the 13º sort: 2 6 1 5 0
  From bit 36 to bit 37
  Vector after the 14º sort: 2 6 1 5 0
  From bit 34 to bit 35
  Vector after the 15º sort: 2 6 1 5 0
  From bit 32 to bit 33
  Vector after the 16º sort: 2 6 1 5 0
  From bit 30 to bit 31
  Vector after the 17º sort: 2 6 1 5 0
  From bit 28 to bit 29
  Vector after the 18º sort: 2 6 1 5 0
  From bit 26 to bit 27
  Vector after the 19º sort: 2 6 1 5 0
  From bit 24 to bit 25
  Vector after the 20º sort: 2 6 1 5 0
  From bit 22 to bit 23
  Vector after the 21º sort: 2 6 1 5 0
  From bit 20 to bit 21
  Vector after the 22º sort: 2 6 1 5 0
  From bit 18 to bit 19
  Vector after the 23º sort: 2 6 1 5 0
  From bit 16 to bit 17
  Vector after the 24º sort: 2 6 1 5 0
  From bit 14 to bit 15
  Vector after the 25º sort: 2 6 1 5 0
  From bit 12 to bit 13
  Vector after the 26º sort: 2 6 1 5 0
  From bit 10 to bit 11
  Vector after the 27º sort: 2 6 1 5 0
  From bit 8 to bit 9
  Vector after the 28º sort: 2 6 1 5 0
  From bit 6 to bit 7
  Vector after the 29º sort: 2 6 1 5 0
  From bit 4 to bit 5
  Vector after the 30º sort: 2 6 1 5 0
  From bit 2 to bit 3
  Vector after the 31º sort: 2 1 0 6 5
  From bit 0 to bit 1
  Vector after the 32º sort: 0 2 6 1 5
  </code></pre>
  
  <p>As you can see in the output, the changes only happens in the 31st and 32nd sort (so, that means the significant bits are found in the last searchs).</p>
  
  <p>Anyone can help me to find my mistake?</p>
  
  <p>Thanks in advance.</p>