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 Connections
Sources
1. Wikipedia: Bucket sort
Worst-case analysisQuote, Worst-case analysis
The worst-case scenario occurs when all the elements are placed in a single bucket.
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.