Radix Sort: Analysis

• Each digit requires n comparisons

• The algorithm is ?(n)

• The preceding lower bound analysis does not apply, because Radix Sort does not compare keys.

• Radix Sort is sometimes known as bucket sort. (Any distinction between the two is unimportant

• Alg. was used by operators of card sorters.

Previous slide

Back to first slide

View graphic version