Bucket Sort
Updated 2026-08-17
INTRODUCTION
English translation pending.
CORE DEFINITION
Bucket sort is a distribution sort that assigns each element to a bucket according to its value, sorts each bucket, and concatenates them in order. It is a classical technique rather than any single inventor's work, and it belongs to the same family as counting sort and radix sort. Its average running time is linear in the number of elements when the keys are uniformly distributed across the value range and the bucket count is chosen to keep each bucket small. The method trades memory and a known key domain for speed, and its worst case becomes quadratic when all elements land in one bucket.
SCAFFOLDING EFFECT
Reduce cognitive load
- Feasibility check: Ask whether keys map onto an ordered numeric range before choosing this sort. - Bucket sizing: Set the bucket count so each bucket holds a small, roughly equal share. - Tail handling: Sort each bucket with a simple method and concatenate only after every bucket is done.
Anchor fast decisions
Sorting becomes cheap when the work is split so finely that each piece can be handled by a trivial method. Because the bucket boundaries encode the ordering, no element ever has to be compared against an element from another bucket: position in the array carries that information. The cost then depends on how evenly the keys spread, since the total work is the sum of the per-bucket sorting costs plus the linear pass to distribute and collect.
MINIMUM ACTION
In progress 0/1Practice this model in one real situation:
account_treeGenealogyexpand_more
menu_bookReferencesexpand_more
Source support: Explicit
- github.comhttps://github.com/kcchien/model-thinkingverified
PRIVATE NOTES · Only visible to you
SAVED Q&A
ENTRY Q&A · Private saving available
Ask with a clear boundary
thinkingmodels answers from published entry context only.
Your question is sent to thinkingmodels. The answer uses public entry context only.
RELATED MODELS