Overview
Bucket Sorts works under the premise of partitioning an array (or list) into a number of buckets and then sorting the buckets individually.
Concept
The way bucket sort works is:
- Set up the empty buckets. Typically these are arrays or some other sort of collection.
- Iterate over the unsorted array and place each object in the bucket it belongs based on a characteristic of the value.
- Sort each non-empty bucket.
- Iterate over the buckets, in order, and pull out all the elements back into the original array.
Algorithmic Complexity
Big-O
| Algorithm | Data Structure | Time Complexity - Best | Time Complexity - Average | Time Complexity - Worst | Worst Case Auxiliary Space Complexity |
|---|---|---|---|---|---|
| Bucket Sort | Array | O(n+k) | O(n+k) | O(n^2) | O(nk) |
Implementation
Java Implementation
Coming soon!
References
Wikipedia: Bucket sort