Databases
StackOverflow2013
Postsdbo
POperformance characteristics of radix sort
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POperformance characteristics of radix sort
    text
    copied!<p>I am reading about performance charactersistics of radix sorting in Robert Sedwick algorithms in C++. Here author mentioned as below in section 10.6</p> <p>Following link is online reference.</p> <p><a href="http://books.google.co.in/books?id=ZCchAeprwvYC&amp;pg=PT605&amp;lpg=PT605&amp;dq=performance+characteristics+of+radix+sorts&amp;source=bl&amp;ots=1aH-jTEDZK&amp;sig=zcIRfsIUn6_QtjhG7WR3IbWtGtA&amp;hl=en&amp;sa=X&amp;ei=sGq9Up69NseprAfx2IG4BA&amp;ved=0CFAQ6AEwBg#v=onepage&amp;q=performance%20characteristics%20of%20radix%20sorts&amp;f=false" rel="nofollow">http://books.google.co.in/books?id=ZCchAeprwvYC&amp;pg=PT605&amp;lpg=PT605&amp;dq=performance+characteristics+of+radix+sorts&amp;source=bl&amp;ots=1aH-jTEDZK&amp;sig=zcIRfsIUn6_QtjhG7WR3IbWtGtA&amp;hl=en&amp;sa=X&amp;ei=sGq9Up69NseprAfx2IG4BA&amp;ved=0CFAQ6AEwBg#v=onepage&amp;q=performance%20characteristics%20of%20radix%20sorts&amp;f=false</a></p> <blockquote> <p>The running time of LSD radix sort for sorting N records with w-byte keys is proportional to Nw, because the algorithm makes w passes over all N keys. This analysis does not depend on the input.</p> <p>For long keys and short bytes, this running time is comparable to N lg N: For example, if we are using a binary LSD radix sort to sort 1 billion 32-bit keys, then w and lg N are both about 32. For shorter keys and longer bytes this running time is comparable to N: For example, if a 16-bit radix is used on 64-bit keys, then w will be 4, a small constant.</p> </blockquote> <p>My question on above text</p> <ol> <li><p>Why author is comparint with N lg N for long keys and short bytes? How author came to conclusing here w and lg N are both 32 here?</p></li> <li><p>Why author is comparing with N for shorter keys and longer bytes? How w is calculated here?</p></li> <li><p>I am not getting what author is meant by short bytes and long bytes here?</p></li> </ol>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload