LSD and MSD sorting - which requires fixed length keys?

Problem Detail: 

I am studying these sorts, but it is still unclear to me which one of these two would require fixed length keys?

Asked By : user2461994

Answered By : hanugm

MSD(Most Significant Digit) radix sort needs fixed length keys as input.

Reason :

LSD(Most Significant Digit) radix sort first sorts the integers based on the least significant digits and then proceeds sorting for most significant digits . So, there is no problem if the keys are of non-equal length because of the reason that MSD has more weight-age.

MSD(Most Significant Digit) radix sort starts with most significant digits and then proceeds sorting to least significant digits , if the given keys are of unequal length , we have to place required number of 0's infront of them to make equal length. Then only we can sort based on most significant digits .

If you are still unclear , then remember the following

'LSD first sorts least significant digits and then sorts the keys with same length in lexicographical order'

"MSD sorts the keys in lexicographical order"

Lexicographical ordering comparison always between keys of same length.

You can remember it by their running times too ,

Running time of LSD is $\ O(n*k_{avg})$ and for MSD is $\ O(n*k)$

where $n=$ # keys to be sorted , $k_{avg}=$average length of keys , $k=$length of a key

So , it shows that LSD assumes each key may have different lengths , so the tme complexity takes average of length's ($k_{avg}$) but MSD assumes each key must be of length '$k$', so its $\ O(k)$ .

Simple example : let us take integers in which one of them has different length and then we try to sort them .

Keys = $23,165,104$

LSD : 1) $2\underline{3},16\underline{5},10\underline{4}$ (compares unit's digits)$\implies 2\underline{3},10\underline{4},16\underline{5}$

2) $\underline{2}3,1\underline{6}5,1\underline{0}4$ (compares ten's digits)$\implies 1\underline{0}4, \underline{2}3,1\underline{6}5$

3) $\underline{1}04,23,\underline{1}65$ (compares hundred's digits)$\implies 23,\underline{1}04, \underline{1}65$

If we do the same for MSD (with out making them equal length by adding 0's in front of them), then the elements will not be sorted :

1) $\underline{2}3,\underline{1}65,\underline{1}04$ (compares MSD's)$\implies \underline{1}65,\underline{1}04,\underline{2}3$

2) $1\underline{6}5,1\underline{0}4,2\underline{3}$ (compares next MSD's )$\implies 1\underline{0}4, 2\underline{3},1\underline{6}5$

3) $10\underline{4},23,16\underline{5}$ (compares hundred's digits)$\implies 10\underline{4}, 16\underline{5},23$

There is no problem if we assume the MSD of an integer as 0 but not in the case of LSD (which leads to error as above)

If we do the same for MSD (After making them equal length by adding 0's in front of them), then the elements will be sorted in correct order:

1) $\underline{0}23,\underline{1}65,\underline{1}04$ (compares MSD's)$\implies \underline{0}23,\underline{1}65,\underline{1}04$

2) $0\underline{2}3,1\underline{6}5,1\underline{0}4$ (compares next MSD's )$\implies 1\underline{0}4, 0\underline{2}3,1\underline{6}5$

3) $10\underline{4},02\underline{3},16\underline{5}$ (compares hundred's digits)$\implies 02\underline{3},10\underline{4}, 16\underline{5}$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29187