Radix exchange sort implementation

algorithmsdatadata structuressorting

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.

Best Answer

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

Related Topic