Overview
Bucket Sort works well when values are spread across a known range and can be assigned to useful buckets.
CoreSource checked
Bucket Sort
Sorts by distributing values into buckets and sorting within each bucket.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Intermediate
- Family
- Distribution Sort
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
bucket partitioninginteger key rangestable orderingdistribution sortordering invariantcomparison or key rulearray rearrangement
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n + k)
Average
O(n + k)
Worst
O(n^2)
Space
O(n + k)
When to Use
- Use Bucket Sort when you need to place values into range-based buckets.
- Use it for uniform numeric data with inputs like values with a known range.
- Use it when ordered output makes later searching, ranking, or presentation easier.
- Use it when the Distribution Sort tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when values are not bounded integers or cannot be mapped cleanly to integer keys.
- Avoid it when a partial order, top-k result, or streaming approach would answer the question with less work.
- Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
- Avoid it when the required output is not sorted values.
What It Does
- Places values into range-based buckets
- Sorts or scans buckets to rebuild the ordered output
Use Cases
- Uniform numeric data
- Pre-bucketing large datasets
- Educational distribution sorting
Inputs
- Values with a known range
- Bucket count or bucket rule
Outputs
- Sorted values
Pseudocode
- 1.Create buckets for the value range
- 2.Place each value into its bucket
- 3.Sort each bucket if needed
- 4.Read buckets in order
- 5.Concatenate bucket contents
Canonical Example
- Input
- values = [5, 1, 4, 2]
- Output
- values = [1, 2, 4, 5]
- Explanation
- Bucket Sort: The algorithm reorders the values so later operations can read them in ascending order.
Implementation Notes
- Keep the input contract explicit: Values with a known range; Bucket count or bucket rule.
- Use this step as the implementation spine: Create buckets for the value range.
- Then preserve the next state change: Place each value into its bucket.
- Test with empty input, one item, duplicates, and already sorted values.
Common Pitfalls
- Bucket Sort needs a bucket rule that keeps bucket sizes reasonably balanced.
- Assuming stability without checking the implementation can reorder equal keys.
- Forgetting to define how equal values and custom comparison rules should behave.
- Returning sorted values without handling empty, invalid, or boundary inputs.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow values falling into buckets and then being read in order.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Create buckets for the value range
bucket-distributionNotes
Bucket Sort operates in O(n + k) time and O(n + k) space within the Distribution Sort family. Often compared with Counting Sort and Radix Sort.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Bucket Sort invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toCounting Sort
Bucket sort and counting sort both exploit key distribution instead of comparison order.
Related Algorithms
Tags
Bucket BasedInteger DataStable Sort