Bucket Sort

1. Create an array of buckets
2. Assign each element to one bucket based on its value (or function of)
3. Sort each bucket. Usually Insertion Sort due to it being faster for small arrays

Note

This sorting algorithm is efficient if you know the distribution of the elements beforehand, and design the bucket assignment rule based on that

See https://www.youtube.com/watch?v=VuXbEb5ywrU

Implementation

class BucketSort(Sort[int]):
    def __init__(self, buckets: int, sorting_method: Sort[int]) -> None:
        self.buckets = buckets
        self.sorting_method = sorting_method
        super().__init__()
 
    def sort(self, array: list[int]) -> list[int]:
        # ASSUMPTION: array consists of integers from 0 to 10
 
        if len(array) <= 1:
            return array
        # INVARIANT: array has 2 or more elements
 
        buckets: list[list[int]] = [list() for _ in range(self.buckets)]
 
        _max = max(array)
        _min = min(array)
        for n in array:
            # NOTE: Scale numbers from 0 to 10 to 0 to self.buckets - 1
            scaled_n = (self.buckets - 1) * (n - _min) // (_max - _min)
            buckets[scaled_n].append(n)
 
        ret: list[int] = []
        for bucket in buckets:
            ret.extend(self.sorting_method.sort(bucket))
        return ret