title: Understanding Radix Sort Algorithm
body: <p>I am trying to understand how this radix sort algorithm works. I am new to algorithms and bits so this isn't coming easy to me. So far i have added these comments to my code to try and make it easier to understand. I am not sure if I have grasped the concept correctly so if anyone can see any problems with my comments/something I am not understanding correctly please help me out :)</p>
  
  <p>Also would anyone be able to explain this line of code to me: <strong>mask = 1 &lt;&lt; bit;</strong></p>
  
  <p><em>My commented code:</em></p>
  
  <pre><code>public static ArrayList&lt;Integer&gt; RadixSort(ArrayList&lt;Integer&gt; a)
      //This method implements the radix sort algorithm, taking an integer array as an input
      {
          ArrayList&lt;Integer&gt; array = CopyArray(a);
          //Created a new integer array called 'array' and set it to equal the array inputed to the method
          //This was done by copying the array entered to the method through the CopyArray method, then setting the results of the method to the new empty array
  
          Integer[] zerobucket = new Integer[a.size()];
          Integer[] onebucket = new Integer[a.size()];
          //Created two more integer arrays to act as buckets for the binary values
          //'zerobucket' will hold array elements where the ith bit is equal to 0
          //'onebucket' will hold array elements where the ith bit is equal to 1
  
          int i, bit;
          //Created two integer variables i &amp; bit, these will be used within the for loops below
          //Both i &amp; bit will be incremented to run the radix sort for every bit of the binary value, for every element in the array
  
          Integer element, mask;
          //Created an integer object called element, this will be used to retrieve the ith element of the unsorted array
          //Created an integer object called mask, this will be used to compare the bit values of each element
  
          for(bit=0; bit&lt;8; ++bit)
          //Created a for loop to run for every bit of the binary value e.g.01000000
          //Change from 8 to 32 for whole integers - will run 4 times slower
          {
              int zcount = 0;
              int ocount = 0;
              //Created two integer variables to allow the 'zerobucket' and 'onebucket' arrays to be increment within the for loop below
  
              for(i=0; i&lt;array.size(); ++i)
              //Created a nested for loop to run for every element of the unsorted array
              //This allows every bit for every binary value in the array
              {
                  element = array.get(i);
                  //Set the variable 'element' to equal the ith element in the array
                  mask = 1 &lt;&lt; bit;
  
                  if ((element &amp; mask) == 0)
                  //If the selected bit of the binary value is equal to 0, run this code
                  {
                      zerobucket[zcount++] = array.get(i);
                      //Set the next element of the 'zerobucket' array to equal the ith element of the unsorted array
                  }
                  else
                  //Else if the selected but of the binary value is not equal to 0, run this code
                  {
                      onebucket[ocount++] = array.get(i);
                      //Set the next element of the 'onebucket' array to equal the ith element of the unsorted array
                  }
              }
  
              for(i=0; i&lt;ocount; ++i)
              //Created a for loop to run for every element within the 'onebucket' array
              {
                  array.set(i,onebucket[i]);
                  //Appended the ith element of the 'onebucket' array to the ith position in the unsorted array
              }
  
              for(i=0; i&lt;zcount; ++i)
              //Created a for loop to run for every element within the 'zerobucket' array
              {
                  array.set(i+ocount,zerobucket[i]);
                  //Appended the ith element of the 'zerobucket' array to the ith position in the unsorted array
              }
          }
          return(array);
          //Returned the sorted array to the method
      }
  </code></pre>
  
  <p>I did not write this code I was given it to try to understand</p>