usrbinenv python3 illustrate how to implement bucket sort algorithm omkar pathak this program will illustrate how to implement bucket sort algorithm wikipedia says bucket sort or bin sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets each bucket is then sorted individually either using a different sorting algorithm or by recursively applying the bucket sorting algorithm it is a distribution sort and is a cousin of radix sort in the most to least significant digit flavour bucket sort is a generalization of pigeonhole sort bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm the computational complexity estimates involve the number of buckets time complexity of solution worst case scenario occurs when all the elements are placed in a single bucket the overall performance would then be dominated by the algorithm used to sort each bucket in this case on log n because of timsort average case on n2k k where k is the number of buckets if k on time complexity is on source https en wikipedia orgwikibucketsort data 1 2 5 0 bucketsortdata sorteddata true data 9 8 7 6 12 bucketsortdata sorteddata true data 4 1 2 1 2 9 bucketsortdata sorteddata true bucketsort sorted true data 1e10 1e10 bucketsortdata sorteddata true import random collection random samplerange50 50 50 bucketsortcollection sortedcollection true usr bin env python3 illustrate how to implement bucket sort algorithm omkar pathak this program will illustrate how to implement bucket sort algorithm wikipedia says bucket sort or bin sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets each bucket is then sorted individually either using a different sorting algorithm or by recursively applying the bucket sorting algorithm it is a distribution sort and is a cousin of radix sort in the most to least significant digit flavour bucket sort is a generalization of pigeonhole sort bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm the computational complexity estimates involve the number of buckets time complexity of solution worst case scenario occurs when all the elements are placed in a single bucket the overall performance would then be dominated by the algorithm used to sort each bucket in this case o n log n because of timsort average case o n n 2 k k where k is the number of buckets if k o n time complexity is o n source https en wikipedia org wiki bucket_sort data 1 2 5 0 bucket_sort data sorted data true data 9 8 7 6 12 bucket_sort data sorted data true data 4 1 2 1 2 9 bucket_sort data sorted data true bucket_sort sorted true data 1e10 1e10 bucket_sort data sorted data true import random collection random sample range 50 50 50 bucket_sort collection sorted collection true
from __future__ import annotations


def bucket_sort(my_list: list, bucket_count: int = 10) -> list:
    

    if len(my_list) == 0 or bucket_count <= 0:
        return []

    min_value, max_value = min(my_list), max(my_list)
    bucket_size = (max_value - min_value) / bucket_count
    buckets: list[list] = [[] for _ in range(bucket_count)]

    for val in my_list:
        index = min(int((val - min_value) / bucket_size), bucket_count - 1)
        buckets[index].append(val)

    return [val for bucket in buckets for val in sorted(bucket)]


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    assert bucket_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]
    assert bucket_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]