most significant v.s. least significant radix sort

Question

If I just need to sort strings composed by ASCII characters, wondering what are the differences between using most significant v.s. least significant radix sorting? I think they should have the same results, but confused by the following statement from below link, and if anyone could help to clarify, it will be great.

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

A most significant digit (MSD) radix sort can be used to sort keys in lexicographic order. Unlike a least significant digit (LSD) radix sort, a most significant digit radix sort does not necessarily preserve the original order of duplicate keys.

thanks in advance, Lin

Answer 1

A LSD radix sort can logically concatenate the sorted bins after each pass (consider them to be a single bin if using a counting / radix sort). A MSD radix sort has to recursively sort each bin independently after each pass. If sorting by bytes, that 256 bins after first pass, 65536 bins after second pass, 16777216 (16 million) bins after third pass, ... .

This is why the old card sorters sort data LSD first. Link to video of one of these in action. The cards are fed in and drop into the chutes face down. In the video, the card sorter drops the cards into bins "0" to "9", then the operator takes the cards from the 0 bin, then takes the cards from the 1 bin and places them on top (behind) the 0 bin cards, then the 2 bin cards go behind the deck, and so on, "concatenating" the cards from the bins. For large decks of cards, above the card sorter would be set of shelves above each bin to place the cards when the decks were too large to hold by hand.

http://www.youtube.com/watch?v=jJH2alRcx4M

Example C++ LSD radix sort for 32 bit unsigned integers, where each "digit" is a byte. Most of the code generates a matrix of counts which are converted into indices that mark the boundaries between variable size bins. The actual radix sort is in the last nested loop.

//  a is input array, b is working array
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    return(a);
}