Algorithms in Java

For many sorting applications, the keys used to define the order of the records for files can be complicated. For example, consider the complex nature...

The key to understanding radix sorts is to recognize that (i) computers generally are built to process bits in groups called machine words, which are...

Suppose that we can rearrange the records of a file such that all those whose keys begin with a 0 bit come before all those...

Using just 1 bit in radix quicksort amounts to treating keys as radix-2 (binary) numbers and considering the most significant digits first. Generalizing, suppose that...

Another way to adapt quicksort for MSD radix sorting is to use three-way partitioning on the leading byte of the keys, moving to the next...

An alternative radix-sorting method is to examine the bytes from right to left. Figure shows how our three-letter word sorting task is accomplished in just...

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...

The primary conclusion that we can draw from the analytic results of Section is that the running time of radix sorts can be sublinear in...