Bucket Sort

Algorithm:

• Create Buckets of same size as of the array
• Distribute element of array into buckets
• Sort each bucket(using any sorting algorithm) and add them back together

When to use:

• When the elements in the array is uniformly distributed.

Time Complexity:

• Best/Average: O(n+k) -takes n times to distribute each element to k buckets and k times to add them back together.
• Worst: O(n2)- when all the elements fall into single bucket

Space Complexity:

• O(n) - usually no extra space is required

In-place: yes
Stable:no

Python Implementation:
def bucket_sort(arr):
   n = len(arr)
   buckets = [[] for _ in range(n)]
   for i in range(n):
        b_index = arr[i]*n
        buckets[b_index] = arr[i]
    result = []
    for bucket in buckets:
          result = result+insertion_sort(bucket)
    return result

def insertion_sort(arr):
   j = len(arr)
   for i in range(j):
        j= i
        while j >0 and arr[j-1] > arr[j]:
            arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1