**Bucket sort** is a sorting algorithm in which the array elements are **distributed into different buckets** **that are** **sorted individually**. The **sorting can be done using some other sorting algorithms** **or** it **can be done by calling the bucket sort function recursively**. This is a **distribution sort**. The complexity of this sorting technique depends on the sorting algorithm used to sort the elements of the bucket. Here, **insertion sort** is used to sort the elements of the bucket.

**Bucket sort can be divided into four phases:**

**1. **Initially, the empty buckets are created.

**2. **The original array is scanned and each element is inserted into the appropriate bucket.

**3. **The elements of each bucket are sorted individually.

**4. **The elements of the buckets are gathered and inserted back to the array.

The **bucket sort** is **applied if the elements of the array are uniformly distributed over a range**. Here, the range of the elements is taken from **0.0** to **1.0**. the buckets are taken according to the range of the elements.

__EXAMPLE:__

Suppose the array elements are:

Suppose, **10 buckets **are created to store the array elements. Here, **the index of the bucket for each element is calculated** as **n*arr[i]** where **n**** is the number of elements** of the array and **arr[i]** is the **ith element** of the array.

Initially, the buckets are **initialized with a ****null value**.

The **first element** of the array is **0.14**. Now, it **will be multiplied by ****5** (here, **n = 5**). Therefore, we get the index of the bucket as: **integer** (**0.14 × 5**) = **0**. Therefore, **the element** will be **added to ****bucket 0**.

Now, the **next element** of the array is **0.25**. The same procedure will be followed. **The index of the bucket is**: integer of **0.25 × 5 ****=**** 1**.

So, this element will be inserted into **bucket 1**.

Similarly, the **indexes of the ****next elements** are:

Integer of **0.10 × 5 ****= 0**

Integer of **0.19 × 5 ****= 0**

Integer of **0.02 × 5 ****= 0**

Therefore, **all the elements** will be inserted into **bucket 0.**

Now, the elements of **bucket ‘0’** **will be sorted using **** insertion sort**. After

Therefore, **all the elements** will be inserted into **bucket 0.**

**For details about insertion sort follow:**** **

**bucket 1**** contains a single element**. Now **it will be inserted back to the original array**.

So, after **sorting the array** will be:

```
INPUT: The array elements
OUTPUT: Array after sorting using bucket sort
PROCESS:
Step 1: [Function ‘bucket_sort(array,n)’]
[Creating a bucket]
Create a list b
for i=0 to n-1 repeat
Set b[i]<-Null
[End of ‘for’ loop]
for i=0 to n-1 repeat
Set bi <- integer of n * j
Create a node with the data arr[i]
Append the node with b[bi]
[End of ‘for’ loop]
for i =0 to n-1 repeat
Sort the list b[i]
[End of ‘for’ loop]
for i=0 to n-1 repeat
put the elements of each list (b[i]) into the original array ‘arr’
[End of ‘for’ loop]
[End of function ‘bucket_sort()’]
Step 2: [Function ‘main()’]
Read n [number of elements]
For i= 0 to n-1 repeat
Read arr[i]
[End of ‘for’ loop]
Call the function ‘bucket_sort(arr,n)’
[End of ‘main’ function]
Step 3: Stop.
```

__CHARACTERISTICS:__

**1. **The input is taken from a particular range.

**2. **It is a **non-comparative sort**.

**3. **The **complexity depends on the number of elements and the number of buckets**.

**4. **The **extra auxiliary memory spaces** are required for the buckets.

**5. **It is a distributive sorting technique.

__TIME COMPLEXITY:__

The complexity of bucket sort depends on the sorting algorithm used to sort the elements of the bucket. Here, insertion sort is used as the sorting algorithm.

__Best case:__

The **best-case** occurs when the elements are distributed in the **buckets uniformly**. Here **n is the number of elements** of the array then the complexity to make the bucket is **O(n)** and the **complexity to sort the elements of the bucket** is **O(k)**.

Therefore,

__Average case:__

The **average case complexity** occurs if the elements are **randomly distributed**. If the elements are not distributed uniformly, then also the bucket sort runs in a linear time.

Therefore,

__Worst case:__

The **worst-case complexity** occurs where the elements are in a very close range in the array. Therefore, they are placed in the same bucket. The insertion sort is used here to sort the elements of the array.

Therefore,

**Worst case **scenario occurs when **all the elements are placed in a single bucket.**

The **worst-case complexity of insertion sort** can be calculated as:

__SPACE COMPLEXITY:__

The **space complexity** of bucket sort is **O(n*k)** where **n**** is the number of elements** and **k** is **the number of buckets**.

__ADVANTAGES:__

**1. **It is a **stable sorting** algorithm.

**2. **If the data are evenly distributed then the sorting is very fast.

**3. **Primarily it does not depend on the comparison.

**4. **As the elements are distributed over a number of arrays, then the array elements to be sorted are small.

**5. **The bucket sort works better if a large degree of parallelism is available.

**6. **It can be used as an external sorting algorithm also.

__DISADVANTAGES:__

**1. **If the distribution of the buckets is not uniform then the complexity of the sorting will increase.

**2. **This sorting cannot be applied to all data types.

**3. **The choice of the bucket is fixed for a particular range of data. If the data is not in that range then the sorting will not work properly.

**4. **This algorithm is written for the input range from 0.0 to 1.0. if the range is changed, then the method of choice of the bucket will also change.

__APPLICATIONS:__

**1. **Bucket sort is used as an external sorting algorithm.

**2. **It is applied while the data are uniformly distributed.

Related

- Radix Sort for positive integer
- Heap Sort Iterative
- Heap Sort using recursion
- Merge Sort Iterative
- Merge Sort using recursion
- Quick Sort using recursion
- Quicksort Iterative
- Insertion Sort
- Selection Sort
- Bubble Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort

Contributed by