bucket

Bucket-Sort

• Using keys as indices into a bucket array has cells indexed from 0 to N − 1
• An entry with key k is placed in the “bucket” B[k], which itself is a sequence (of entries with key k).
• runs in O(n + N) time and uses O(n + N) space, efficient when the range N of values for the keys is small
• stable

Radix-Sort

• sorts a sequence S of entries with keys that are pairs, by applying a stable bucket-sort on the sequence twice
• first sort using the second component and then again using the first component.