What is the time complexity of bucket sort?

Best case O(n + b). Average case O(n + n²/b + b). Worst case O(n²). Space complexity is O(n + b). Assumes values are roughly uniform; skewed data collapses into one bucket.

Bucket sort

medium

Splits by value rather than by position, so concatenating the buckets needs no merge step. Load the 'few unique' preset to watch every value land in one bucket and the whole thing degenerate.

Best O(n + b)Average O(n + n²/b + b)Worst O(n²)Space O(n + b)StableNeeds extra memory

Loading the bucket sort engine…

Where to go next

Counting sort

medium

Sorting with zero comparisons.

Radix sort

medium

Sort by the last digit, then the next, and it comes out ordered.

Hash table with chaining

medium

Collisions share a bucket, and load factor is everything.