Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Distribution Sorting

The final class of sorting algorithm considered in this chapter consists of algorithms that sort by distribution . The unique characteristic of a distribution sorting algorithm is that it does not make use of comparisons to do the sorting.

Instead, distribution sorting algorithms rely on a priori knowledge about the universal set from which the elements to be sorted are drawn. For example, if we know a priori that the size of the universe is a small, fixed constant, say m, then we can use the bucket sorting algorithm described in Section .

Similarly, if we have a universe the elements of which can be represented with a small, finite number of bits (or even digits, letters, or symbols), then we can use the radix sorting algorithm given in Section .

Bucket Sort
Radix Sort