Bucket Sort

Explanation

- **Bucket Sort** is a distribution-based sorting algorithm that divides the range of the input elements into a number of buckets, sorts each bucket, and then concatenates the sorted buckets.
-

• Steps:

  • Divide the input array into n buckets.
  • Sort each bucket individually (usually using a different sorting algorithm).
  • Concatenate the sorted buckets to get the final sorted array.

• Time Complexity:

  • Best Case, Average Case: O(n + k) where n is the number of elements and k is the number of buckets.
  • Worst Case: O(n^2) (if all elements fall into a single bucket).