Radix Sort for Negative Integers

sorting language-agnostic radix-sort radix
gtkesh picture gtkesh · Mar 9, 2013 · Viewed 16.7k times · Source

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?

Thank you!

Answer

Peter Wooster picture Peter Wooster · Mar 9, 2013

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.

Related questions

What is the difference between bucket sort and radix sort?

Bucket sort and radix sort are close cousins; bucket sort goes from MSD to LSD, while radix sort can go in both "directions" (LSD or MSD). How do both algorithms work, and in particular how do they differ?

Read More
In-Place Radix Sort

This is a long text. Please bear with me. Boiled down, the question is: Is there a workable in-place radix sort algorithm? Preliminary I've got a huge number of small fixed-length strings that only use the letters “A”, “C”, “G” …

Read More
How can I pair socks from a pile efficiently?

Yesterday I was pairing the socks from the clean laundry and figured out the way I was doing it is not very efficient. I was doing a naive search â€” picking one sock and "iterating" the pile in order to find …

Read More