I am trying to implement radix sort for integers, including negative integers. For non-negative ints, I was planning to create a queue of 10 queues correspondingly for the digits 0-9 and implement the LSD algorithm. But I was kind of confused with negative integers. What I am thinking now, is to go ahead and create another queue of 10 queues for them and separately sort them and then at the end, I will gave 2 lists, one containing negative ints sorted and the other containing non-negative ints. And finally I would merge them.
What do you think about this? Is there more efficient way to handle with negative integers?
You can treat the sign as a special kind of digit. You sort the pile on the units, then the tens, etc. and finally on the sign. This does produce a reversed order for the negatives, you then simply reverse the contents of that bucket. It's how old mechanical card sorters worked.