A sort that distributes elements into a number of buckets covering ranges of the input, sorts each bucket individually, often with another sort, and then concatenates the buckets; fast on average when the input is spread roughly evenly across the range.
Facts
Time ComplexityO(n) average time under uniform distribution; worst case O(n squared) with insertion sort when all elements fall in one bucket 1 Time Complexity
Time Complexity (category) Connections
In Field
Uses Design Technique
Source Wikipedia: Bucket sort
Sources
1. Wikipedia: Bucket sort
Worst-case analysis
The worst-case scenario occurs when all the elements are placed in a single bucket.
Uses Design Technique: Recursion, Lead
Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.
In Group: Distribution and Integer Sorting Algorithms, Lead section
works by distributing the elements of an array into a number of buckets
View the SourceWikidata: Bucket Sort
Wikidata Q6787153, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.