Bucket Sort


Bucket Sorts works under the premise of partitioning an array (or list) into  a number of buckets and then sorting the buckets individually.


The way bucket sort works is:

  1. Set up the empty buckets. Typically these are arrays or some other sort of collection.
  2. Iterate over the unsorted array and place each object in the bucket it belongs based on a characteristic of the value.
  3. Sort each non-empty bucket.
  4. Iterate over the buckets, in order, and pull out all the elements back into the original array.

Algorithmic Complexity


AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
Bucket SortArray O(n+k) O(n+k) O(n^2) O(nk)



Java Implementation

Coming soon!


Wikipedia: Bucket sort


<- back