Is radix sort the only non-comparison sorting algorithm?

Question

As the title says, is radix sort the only non-comparison sorting algorithm? My guess is yes.

Answer 1

No - there's counting sort and bucket sort also, among others. Check the Wikipedia article for more info.

Answer 2

Any set can be sorted by not using comparisons.

The process is

• decide on a manageable size of input domain M you can handle to record in a manageable array. For chars(8-bit) the domain would be 0-255.
• split the input in some orderly fashion into the array.
• repeat and rinse if the input is still not completely considered i.e. all bits in M has not been considered.

For example an 32 bit, M, integer sort could be carried out as:

• look at the first 8 bits, put (references, pointers or what your lang has available), in the 8-bit range. put them in an array [0-255], now you have a coarse(ballpark) ordering of your values.
• look at the next 8 bits, put them in a similar array, keep a reference to the first ordering. The next 8x2 bits are handled the same way. To extract you follow the links from the first set.

Radix sort uses digits and have 2 variants, (MSB to LSB) and (LSB to MSB).

Counting sort uses only the first step

Bucket sort is usually mentioned when referring to a mix of counting and a comparison sorts.

Interestingly, for quite a few use-cases, comparison sorts comes up short.