Radix exchange sort implementation?

Question

I need a little help understanding the implementation of radix exchange sort algorithm.

Radix exchange (I don't know if it's the exact name in english based literature) is a lot similar to quicksort, but uses binary representation of numbers.

Firts we look the highest digit in binary representation, and then using two indexes (from the beginning of the array and from the end, we increment the first if the given digit is 0, and decrement the other if the given digit is 1). Then we swap two numbers, and then continue the work until i = j (the indexes are equal). Then we have two separate partitions and sort them using the second most important digit and so on...

Mainly, I have a few questions:

1. Is this algorithm really called radix exchange or does it have some other, more commonly used name?

2. What are the advantages of this algorithm? It seems like a lot of work, and not very effective?

3. Where can I see an example of implementation of the algorithm? Maybe it will be a little more clearer on what it really is, because it's really confusing for me at the moment.

Answer 1

it sounds like the time complexity would be O(n*k) and space complexity is O(k) with k being the number of bits of each element

in C++ it would be

radixQsort(int* arrb, int* arre, int rad=INT_BITS){
 if(arrb==arre)return;
 int* arrm = std::partition(arrb,arre,[rad](a){return !(a&(1<<rad));});
 radixQsort(arrb,arrm,rad-1);
 radixQsort(arrm,arre,rad-1);
}

this is implemented using the partition in the standard library which works like the partition you described

Answer 2

1. In contrast to quick-sort, radix sort uses "internal representation" of the values which are sorted. I.e. it doesn't simply compare them with <>. And it is really effective when you take several bits, not one, on each sorting pass. 4 bits, maybe 8. So you will divide the array onto 256 groups on each pass in the latter case. And have only 4 passes for 32-bit integers.

https://en.wikipedia.org/wiki/Radix_sort