title: MSD Radix-sort (lexicographic order) in C++
body: <p>Thanks for reading this post.</p>
  
  <p>I wanted to create an MSD radix sort that's supposed to sort a vector of unsigned integers in lexicographic (alphabetic) order. </p>
  
  <p><em>Given "1, 3, 32, 1254, 3, 165, 50000, 11, 213"</em></p>
  
  <p><em>Sorted "1, 11, 1254, 165, 213, 3, 3, 32, 50000"</em></p>
  
  <p>Since I think I should do it recursively, I tried to capture the highest digits and call the function recursively with the next digit for all the numbers. However, I just realized that I got the logic wrong since this would sort in the regular numeric order as I iterated on all numbers from the highest digit with the same digit (e.g. the 5th one, which could be 0 for numbers that have no more than 5 digits). So I abandoned this algorithm but could not come up with new thoughts.</p>
  
  <p>Since this could deal with any numbers, it should operate recursively. I have some ideas now, but they seemed not to be working:</p>
  
  <ol>
  <li>Since this is similar to an alphabetic order, I could change the integers into strings by using <code>std::to_string()</code>, and use <code>std::sort()</code>, but I don't think this is a good option since it's no longer seeking an algorithm outcome, and I don't know how to change the string back to an <strong>unsigned</strong> integer.</li>
  <li>I wanted to find the largest digit by repeatedly dividing 10 until the result is less than 10, then sort by this digit for each number, but it's not working since the digits of the number vary, and I cannot do it recursively as I already lost most part of the data by dividing. I think I am still sticking to the numeric sorting model. I don't really see the steps that we could make recursion possible when we cannot determine a fixed digit or any possible point to compare so we could implement the recursive sort.</li>
  </ol>
  
  <p>Do you have any implementation ideas about this different kind of number sorting?</p>